Amazon

2020-10-10

## 1081. Smallest Subsequence of Distinct Characters

### Question:

Return the lexicographically smallest subsequence of `s` that contains all the distinct characters of `s` exactly once.

Note: This question is the same as: LeetCode Question 316

#### Example 1:

``````Input: s = "bcabc"
Output: "abc"
``````

#### Example 2:

``````Input: s = "cbacdcbc"
Output: "acdb"
``````

Constraints:

• `1 <= s.length <= 1000`
• `s` consists of lowercase English letters.

### Solution:

Counter the last appreance index and use a visited array to check the occurance.

``````class Solution {
public String smallestSubsequence(String s) {
Stack<Integer> stack = new Stack<>();
int[] lastIndex = new int[26];
boolean[] visited = new boolean[26];
for (int i = 0; i < s.length(); i++) {
lastIndex[s.charAt(i) - 'a'] = i;
}
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - 'a';
if (visited[index]) continue;
while(!stack.isEmpty() && stack.peek() > index && i < lastIndex[stack.peek()]) {
visited[stack.pop()] = false;
}
stack.push(index);
visited[index] = true;
}
StringBuilder sb = new StringBuilder();
for (int i : stack) {
sb.append((char)('a' + i));
}
return sb.toString();
}
}
``````