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.

How to Solve

  1. Store occurrences of every character
  2. For every character in string, do following-
    1. decrement number of characters remaining in the string to be analysed
    2. if character is already present in stack, don’t bother
    3. if current character is smaller than last character in stack which occurs later in the string again, it can be removed and added later e.g. stack = bc remaining string abc then a can pop b and then c
    4. add current character in stack and mark it as visited
  3. pop character from stack and build answer string from back

Test Cases

Example 1:

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

Example 2:

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

Solution

class Solution {
    public String removeDuplicateLetters(String s) {

        int[] occ = new int[26];
        boolean[] visited = new boolean[26];
        char[] ch = s.toCharArray();
        for(char c: ch){
            occ[c - 'a']++;
        }
        Stack<Character> stack = new Stack<>();
        int index;
        for(char c: ch){
            index= c-'a';
            occ[index]--;
            if(visited[index]) continue;
            while(!stack.isEmpty() && c < stack.peek() && occ[stack.peek() - 'a'] != 0){
                visited[stack.pop() - 'a']=false;
            }
            stack.push(c);
            visited[index]=true;
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.insert(0,stack.pop());
        }
        return sb.toString();
    }
}
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack, occ, visited = [], {}, {}
        for c in s:
            occ[c] = occ.get(c, 0) + 1
            visited[c] = False
        for c in s:
            occ[c] -= 1
            if visited[c]:
                continue
            while stack and c < stack[-1] and occ[stack[-1]] > 0:
                visited[stack.pop()] = False
            visited[c] = True
            stack.append(c)
        return ''.join(stack)
Time Complexity: O(n)
Space Complexity: O(n)