Remove Duplicate Letters

Share

Remove duplicate letters so each letter appears once. Return lexicographically smallest result.

Example 1
Input: s="bcabc" → Output: "abc"
Example 2
Input: s="cbacdcbc" → Output: "acdb"

Solution Approach

Use a monotonic stack with visited set. For each character, pop larger chars if they appear later.

  • Count remaining occurrence of each character
  • Use stack and visited set
  • For each char: if visited skip
  • While stack top > curr and top appears later: pop it, mark unvisited
  • Push current, mark visited
Java
public String removeDuplicateLetters(String s) {
    int[] count = new int[26];
    boolean[] inStack = new boolean[26];
    for (char c : s.toCharArray()) count[c - 'a']++;
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        count[c - 'a']--;
        if (inStack[c - 'a']) continue;
        while (!stack.isEmpty() && stack.peek() > c && count[stack.peek() - 'a'] > 0) {
            inStack[stack.pop() - 'a'] = false;
        }
        stack.push(c);
        inStack[c - 'a'] = true;
    }
    StringBuilder sb = new StringBuilder();
    for (char c : stack) sb.append(c);
    return sb.reverse().toString();
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)