Remove duplicate letters so each letter appears once. Return lexicographically smallest result.
Input: s="bcabc" → Output: "abc"
Input: s="cbacdcbc" → Output: "acdb"
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
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)