Log inSign up
mediumleetcodeNot Started

Remove Duplicate Letters

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

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 problem is identical to LeetCode 1081: Smallest Subsequence of Distinct Characters.

Example 1 · Example:

Input: s = "bcabc"
Output: "abc"
Explanation: "abc" is the smallest lexicographical result containing a, b, and c once.

Example 2 · Example:

Input: s = "cbacdcbc"
Output: "acdb"
Explanation: Possible unique permutations include "cbad", "bacd", "acdb", etc. "acdb" is the lexicographically smallest.

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master monotonic stack operations with future-occurrence guards.
  • Formulate lexicographical minimization greedily.
  • Maintain visited boolean bitsets in O(1) space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Selecting unique elements from a stream in smallest/largest lexicographical order.
  • Monotonic stack with future availability checks.

Algorithmic Decision Tree:

  • Monotonic Increasing Stack
  • Greedy Lexicographical Optimization

Connected Patterns:

Smallest Subsequence of Distinct CharactersNext Greater ElementDaily Temperatures

1. Recursive Greedy Selection

Intuition

Count character frequencies in s. Find the index of the first character c that can be safely selected (i.e. all other distinct characters still appear at or after this index). Pick the smallest such character, remove all occurrences of it from the remaining suffix, and recurse.

When to apply: Basic functional recursive solution.

Algorithm

  1. If s is empty, return "".
  2. Count character frequencies.
  3. Find the leftmost index pos where remaining suffix covers all unique characters.
  4. Pick minChar = s[pos].
  5. Filter minChar from s.substr(pos + 1) and recurse.
  6. Return minChar + recurse(filteredSuffix).

Recursive Greedy Selection

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [b, c, a, b, c]
Current operationSTEP 1 OF 6
Observation: Count occurrences of all characters: 'b' appears 2 times, 'c' appears 2 times, 'a' appears 1 time
Visual state
Values and pointers at this exact step
array
S
b
c
a
b
c
0
1
2
↑ SMALLEST CHAR: 'a'
3
4
Variables at this step
counts
{"b":2,"c":2,"a":1}
candidate
a
suffixContainsAll
true
picked
a
Check / comparison
Counts in 'bcabc': { b: 2, c: 2, a: 1 }. Smallest char is 'a' at idx 2.
Decision / next transition
Suffix starting at idx 2 ('abc') contains all unique characters {a, b, c}. Pick 'a'.
Why this step matters

Observation: Count occurrences of all characters: 'b' appears 2 times, 'c' appears 2 times, 'a' appears 1 time.

Decision: Smallest letter in alphabet is 'a' (at index 2). Suffix after index 2 contains 'b' and 'c', so all remaining letters can still be formed! Pick 'a'.

Invariant: Always pick the lexicographically smallest character whose suffix contains all remaining unique characters.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 std::string removeDuplicateLetters(std::string s) {
9 if (s.empty()) return "";
10 int count[26] = {0};
11 for (char c : s) count[c - 'a']++;
12
13 int pos = 0;
14 for (int i = 0; i < (int)s.size(); ++i) {
15 if (s[i] < s[pos]) pos = i;
16 if (--count[s[i] - 'a'] == 0) break;
17 }
18
19 char chosen = s[pos];
20 std::string remainder = s.substr(pos + 1);
21 remainder.erase(std::remove(remainder.begin(), remainder.end(), chosen), remainder.end());
22 return chosen + removeDuplicateLetters(remainder);
23 }
24};
25
26int main() {
27 Solution sol;
28 std::cout << sol.removeDuplicateLetters("bcabc") << std::endl; // "abc"
29 std::cout << sol.removeDuplicateLetters("cbacdcbc") << std::endl; // "acdb"
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(26 * N) — At most 26 recursive levels, each scanning suffix of length up to N.
  • Space complexity: O(26 * N) recursion stack

Why Brute Force Doesn't Scale:

Monotonic stack evaluates and resolves character order in a single linear pass.

Using 26-element integer and boolean arrays guarantees O(1) auxiliary space.

2. Monotonic Stack with Remaining Character Counter

Intuition

Count total character frequencies in remaining. Maintain inStack[26] boolean array and a character stack. For each character c: decrement remaining[c]. If inStack[c] is true, continue. While stack is not empty, c < stack.top(), and remaining[stack.top()] > 0: pop stack.top() and mark inStack[top] = false. Push c and mark inStack[c] = true.

When to apply: Alternative stack-based implementation.

Algorithm

  1. Count frequencies in remaining[26].
  2. Initialize inStack[26] = false and stack = [].
  3. For each character c in s:
  4. remaining[c]--
  5. If inStack[c]: continue.
  6. While stack.length > 0 && c < stack.top() && remaining[stack.top()] > 0:
  7. inStack[stack.pop()] = false.
  8. stack.push(c)
  9. inStack[c] = true
  10. Return stack joined as string.

Monotonic Stack with Remaining Character Counter

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [b, c, a, b, c]
Current operationSTEP 1 OF 6
Observation: Precompute remaining counts for all characters
Visual state
Values and pointers at this exact step
array
S
b
c
a
b
c
0
↑ PUSH 'b'
1
2
3
4
Variables at this step
stack
["b"]
seen
{"b":true}
remaining
{"b":1,"c":2,"a":1}
Check / comparison
Count map: {b:2, c:2, a:1}. Stack empty. Push 'b'.
Decision / next transition
Stack: ['b']. seen: {b: true}. remaining['b'] = 1.
Why this step matters

Observation: Precompute remaining counts for all characters. Stack is empty.

Decision: Push 'b' onto stack. Mark 'b' in seen set. Decrement remaining count of 'b'.

Invariant: Characters in stack maintain monotonically increasing order when possible.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string removeDuplicateLetters(std::string s) {
8 int remaining[26] = {0};
9 for (char c : s) remaining[c - 'a']++;
10
11 bool inStack[26] = {false};
12 std::string stack = "";
13
14 for (char c : s) {
15 remaining[c - 'a']--;
16 if (inStack[c - 'a']) continue;
17
18 while (!stack.empty() && c < stack.back() && remaining[stack.back() - 'a'] > 0) {
19 inStack[stack.back() - 'a'] = false;
20 stack.pop_back();
21 }
22 stack.push_back(c);
23 inStack[c - 'a'] = true;
24 }
25 return stack;
26 }
27};
28
29int main() {
30 Solution sol;
31 std::cout << sol.removeDuplicateLetters("bcabc") << std::endl; // "abc"
32 std::cout << sol.removeDuplicateLetters("cbacdcbc") << std::endl; // "acdb"
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — Each character is pushed and popped at most once.
  • Space complexity: O(1) (26 characters)

3. Monotonic Stack with Last Occurrence Index (Optimal)

Intuition

Precompute lastSeen[26] where lastSeen[c - 'a'] stores the last index of character c in s. Maintain boolean seen[26] and stack string. Loop i from 0 to n - 1: if seen[s[i] - 'a'] is true, skip. While stack is not empty, s[i] < stack.back(), and lastSeen[stack.back() - 'a'] > i: pop stack.back() and mark seen[popped] = false. Append s[i] to stack and mark seen[s[i] - 'a'] = true.

When to apply: The standard gold standard solution for clean code and maximum execution speed.

Algorithm

  1. Precompute lastSeen[26] with the last index of each character.
  2. Initialize seen[26] = false and stack = "".
  3. For i from 0 to n - 1:
  4. c = s[i]
  5. If seen[c - 'a']: continue.
  6. While !stack.empty() && c < stack.back() && lastSeen[stack.back() - 'a'] > i:
  7. seen[stack.back() - 'a'] = false
  8. stack.pop_back()
  9. stack.push_back(c)
  10. seen[c - 'a'] = true
  11. Return stack.

Monotonic Lexicographical Stack with Last-Occurrence Lookahead

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [b, c, a, b, c]
Current operationSTEP 1 OF 6
Observation: Last occurrence map: a: 2, b: 3, c: 4
Visual state
Values and pointers at this exact step
array
S
b
c
a
b
c
0
↑ i=0: 'b'
1
2
3
4
Variables at this step
lastIndex
{"a":2,"b":3,"c":4}
stack
["b"]
seen
{"b":true}
Why this step matters

Observation: Last occurrence map: a: 2, b: 3, c: 4. Read s[0] = 'b'.

Decision: Stack empty: push 'b', mark seen['b'] = true.

Invariant: Stack elements remain unique and in lexicographical attempt order.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string removeDuplicateLetters(std::string s) {
8 int lastSeen[26] = {0};
9 int n = s.size();
10 for (int i = 0; i < n; ++i) {
11 lastSeen[s[i] - 'a'] = i;
12 }
13
14 bool seen[26] = {false};
15 std::string stack = "";
16
17 for (int i = 0; i < n; ++i) {
18 char c = s[i];
19 if (seen[c - 'a']) continue;
20
21 while (!stack.empty() && c < stack.back() && lastSeen[stack.back() - 'a'] > i) {
22 seen[stack.back() - 'a'] = false;
23 stack.pop_back();
24 }
25 stack.push_back(c);
26 seen[c - 'a'] = true;
27 }
28 return stack;
29 }
30};
31
32int main() {
33 Solution sol;
34 std::cout << sol.removeDuplicateLetters("bcabc") << std::endl; // "abc"
35 std::cout << sol.removeDuplicateLetters("cbacdcbc") << std::endl; // "acdb"
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass to record lastSeen, and single linear pass with amortized O(1) stack pushes/pops.
  • Space complexity: O(1) (26 characters)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Greedy SelectionO(26 * N)O(26 * N)Pure recursive selection finding leftmost smallest character with complete remaining set.String slicing and recursion overhead.
2.Monotonic Stack with Frequency CounterO(N)O(1) (26 characters)Tracks remaining counts of characters instead of indices.Requires decrementing counts at every iteration.
3.Monotonic Stack with Last Occurrence Array (Optimal)OptimalO(N) strictlyO(1) extra spaceDirect O(1) condition lastSeen[top] > i, zero decrement overhead, fastest single-pass stack.None.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Popping a character when it does NOT appear again later in the string (lastSeen <= i), losing it from the output.

Pitfall 2:

Not skipping characters that are already in the stack (seen[c] == true).

Crucial Edge Cases to Validate:

  • String already sorted with distinct characters (s = abc): No elements popped, returns abc.
  • Reverse sorted string with duplicates (s = cba): All lastSeen indices are current, cannot pop, returns cba.
  • All identical characters (s = aaaa): Seen set skips duplicate as, returns single a.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the twin conditions for popping: c < stack.top() AND lastSeen[stack.top()] > i.
  2. Highlight that each character is pushed and popped at most once, proving strict O(N) runtime.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can we only pop stack.top() if lastSeen[stack.top()] > i?

Back to DSA Sheet