Remove Duplicate Letters in Lexicographic Order
Solve this Problems, remove duplicate letters so every letter appears exactly once in the result, keeping the relative order of the letters you keep — and among every arrangement that satisfies those two rules, return the lexicographically smallest one.
The greedy rule: a character should give way to a later, smaller character only if it's guaranteed to reappear afterward — otherwise removing it loses that letter from the answer entirely. A single pass with a stack applies this rule the instant each character arrives: pop anything bigger off the top as long as a precomputed "last occurrence" table confirms it will show up again later, then push the new character (skipping it entirely if it's already on the stack). That's the same decision the brute force's recursive "find the safe cutoff, then rebuild" approach makes — just recognized immediately instead of rediscovered by rescanning from scratch after every pick.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ s.length ≤ 15 - ◆
s consists only of lowercase English letters
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursively Recompute the Cutoff and Rebuild the String
BrutePick the string's first character one letter at a time. Scan forward from the start, tracking the smallest character seen so far, but stop the scan the instant the current position is that character's very last occurrence anywhere in the string — going further would risk losing access to it forever. The smallest character found within that safe window is the next output character; remove every occurrence of it from everything after that position, and recurse on what's left. Since at most 26 distinct letters exist, this makes at most 26 recursive calls, each doing a fresh O(n) scan and rebuild — O(n·Σ) total, where Σ is the alphabet size.
O(n·Σ)O(n)1class Solution {
2 public String removeDuplicateLettersLex(String s) {
3 if (s.isEmpty()) return "";
4 int[] last = new int[26];
5 for (int i = 0; i < s.length(); i++) {
6 last[s.charAt(i) - 'a'] = i;
7 }
8 int pos = 0;
9 for (int i = 0; i < s.length(); i++) {
10 if (s.charAt(i) < s.charAt(pos)) pos = i;
11 if (i == last[s.charAt(i) - 'a']) break;
12 }
13 char ch = s.charAt(pos);
14 StringBuilder suffix = new StringBuilder();
15 for (int i = pos + 1; i < s.length(); i++) {
16 if (s.charAt(i) != ch) suffix.append(s.charAt(i));
17 }
18 return ch + removeDuplicateLettersLex(suffix.toString());
19 }
20}Optimal — Single-Pass Monotonic Stack With Availability Tracking
OptimalProcess the string once, left to right, keeping a stack that stays as small (lexicographically) as possible. Skip a character entirely if it's already on the stack — it can't help to have it twice. Otherwise, before pushing it, pop anything on top that is both bigger than it AND still has a later occurrence still to come (checked with a precomputed last-occurrence table) — popping is only safe when that letter can still be added back in later. This recognizes, the moment each character arrives, exactly the same "safe cutoff" decision the brute force rediscovers with a fresh scan every recursive call. Every letter is pushed at most once and popped at most once, giving O(n) total.
O(n)O(n)1class Solution {
2 public String removeDuplicateLettersLex(String s) {
3 int[] lastIndex = new int[26];
4 for (int i = 0; i < s.length(); i++) {
5 lastIndex[s.charAt(i) - 'a'] = i;
6 }
7 boolean[] inStack = new boolean[26];
8 Deque<Character> stack = new ArrayDeque<>();
9 for (int i = 0; i < s.length(); i++) {
10 char c = s.charAt(i);
11 if (inStack[c - 'a']) continue;
12 while (!stack.isEmpty() && stack.peek() > c && lastIndex[stack.peek() - 'a'] > i) {
13 inStack[stack.pop() - 'a'] = false;
14 }
15 stack.push(c);
16 inStack[c - 'a'] = true;
17 }
18 StringBuilder sb = new StringBuilder();
19 while (!stack.isEmpty()) sb.append(stack.pollLast());
20 return sb.toString();
21 }
22}