Remove Duplicate Letters

Amazon

ByteDance

Facebook

2020-10-09

316. Remove Duplicate Letters

Question:

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

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

Example 1:

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

Example 2:

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

Constraints:

1 <= s.length <= 104
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 removeDuplicateLetters(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();
    }
}