Smallest Subsequence of Distinct Characters

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();
    }
}