Problem Description

You are given a string s that contains lowercase English letters. Your task is to remove duplicate letters from the string so that each letter appears exactly once. Among all possible results after removing duplicates, you need to return the one that is lexicographically smallest.

Lexicographical order means dictionary order - for example, "abc" comes before "acb" because at the first differing position, 'b' comes before 'c' in the alphabet.

For example:

• If s = "bcabc", the output should be "abc" (each letter appears once and it's the smallest possible arrangement)
• If s = "cbacdcbc", the output should be "acdb"

The key challenge is that you can't simply take the first occurrence of each character or sort them alphabetically. You need to strategically choose which occurrence of each duplicate letter to keep, ensuring that:

1. Every letter from the original string appears exactly once in the result
2. The resulting string is the smallest possible in lexicographical order

The solution uses a greedy approach with a stack to build the result. It tracks the last occurrence of each character and uses this information to decide whether to remove characters from the stack when a smaller character is encountered. The algorithm maintains a stack of characters and a set to track which characters are already in the result. When processing each character, if it's not already in the result and there are larger characters in the stack that will appear again later, those larger characters are popped to make room for the smaller one, ensuring the lexicographically smallest result.

Intuition

To build the lexicographically smallest string, we need to make greedy choices at each step. The key insight is that when we encounter a character, we should ask: "Can I place this character in a better position by removing some larger characters that come before it?"

Think of it like arranging people in a line by height, where you want the shortest people in front. If a tall person is currently in line but you know they'll show up again later, you can remove them now to let a shorter person take their place in front.

The critical realization is that we can only remove a character from our current result if we know it will appear again later in the string. This is why we need to track the last occurrence of each character - it tells us whether we'll have another chance to include that character.

Here's how the thinking evolves:

1. Greedy choice: When we see a smaller character, we want it to appear as early as possible in our result to make the string lexicographically smaller.

2. Safe removal condition: We can only remove a character from our current result if:

   • The character we want to remove is larger than the current character (this improves lexicographical order)
   • That character appears again later in the string (so we won't lose it completely)

3. Stack structure: A stack naturally supports this "backtracking" behavior - we can build our result character by character, and when we find a better option, we can pop characters off the top (remove recent additions) to make room for the smaller character.

4. Avoiding duplicates: We need to track which characters are already in our result to avoid adding duplicates. If we encounter a character that's already in our result, we skip it because we've already placed it in its optimal position.

The algorithm essentially simulates making the best local decision at each step while maintaining the ability to revise previous decisions when a better option becomes available, as long as we won't lose any characters permanently.

Solution Approach

The implementation uses a monotonic stack pattern combined with a greedy approach. Here's how the solution works step by step:

Data Structures Used:

1. Dictionary last: Maps each character to its last occurrence index in the string
2. Stack stk: Builds the result string character by character
3. Set vis: Tracks which characters are currently in the stack

Algorithm Steps:

1. Preprocessing - Build the last dictionary:

   last = {c: i for i, c in enumerate(s)}

   This records the rightmost index where each character appears. For example, if s = "bcabc", then last = {'b': 3, 'c': 4, 'a': 2}.

2. Main iteration through the string: For each character c at index i:

   a. Skip if already in result:

   if c in vis:
       continue

   If the character is already in our stack (tracked by vis), we skip it since we only want each character once.

   b. Pop larger characters that appear later:

   while stk and stk[-1] > c and last[stk[-1]] > i:
       vis.remove(stk.pop())

   This is the core logic. While the stack is not empty AND the top character is greater than the current character AND that top character will appear again later (its last occurrence is after the current index), we:

   • Pop the character from the stack
   • Remove it from the vis set

   c. Add current character:

   stk.append(c)
   vis.add(c)

   Push the current character onto the stack and mark it as visited.

3. Build the final result:

   return ''.join(stk)

   Convert the stack to a string.

Example Walkthrough with s = "bcabc":

• last = {'b': 3, 'c': 4, 'a': 2}
• Index 0, c = 'b': Stack becomes ['b'], vis = {'b'}
• Index 1, c = 'c': Stack becomes ['b', 'c'], vis = {'b', 'c'}
• Index 2, c = 'a':
  • 'a' < 'c' and 'c' appears later (at index 4), so pop 'c'
  • 'a' < 'b' and 'b' appears later (at index 3), so pop 'b'
  • Stack becomes ['a'], vis = {'a'}
• Index 3, c = 'b': Stack becomes ['a', 'b'], vis = {'a', 'b'}
• Index 4, c = 'c': Stack becomes ['a', 'b', 'c'], vis = {'a', 'b', 'c'}
• Result: "abc"

The time complexity is O(n) where n is the length of the string, as each character is pushed and popped at most once. The space complexity is O(1) since we only store at most 26 lowercase letters.

Example Walkthrough

Let's walk through the solution with s = "cbacdcbc" to see how the greedy stack approach works.

Step 1: Preprocessing First, we identify the last occurrence of each character:

• last = {'c': 7, 'b': 6, 'a': 2, 'd': 4}

Step 2: Process each character

Starting with empty stack = [] and visited = {}

Index 0: c = 'c'

• 'c' not in visited
• Stack is empty, so add 'c'
• stack = ['c'], visited = {'c'}

Index 1: c = 'b'

• 'b' not in visited
• Check stack top: 'c' > 'b' and 'c' appears later (index 7 > 1)
• Pop 'c' from stack
• Add 'b'
• stack = ['b'], visited = {'b'}

Index 2: c = 'a'

• 'a' not in visited
• Check stack top: 'b' > 'a' and 'b' appears later (index 6 > 2)
• Pop 'b' from stack
• Add 'a'
• stack = ['a'], visited = {'a'}

Index 3: c = 'c'

• 'c' not in visited
• Check stack top: 'a' < 'c', no need to pop
• Add 'c'
• stack = ['a', 'c'], visited = {'a', 'c'}

Index 4: c = 'd'

• 'd' not in visited
• Check stack top: 'c' < 'd', no need to pop
• Add 'd'
• stack = ['a', 'c', 'd'], visited = {'a', 'c', 'd'}

Index 5: c = 'c'

• 'c' already in visited, skip

Index 6: c = 'b'

• 'b' not in visited
• Check stack top: 'd' > 'b' but 'd' doesn't appear later (index 4 < 6)
• Cannot pop 'd', so check if we can add 'b'
• Since 'd' > 'b' and we can't remove 'd', we need to reconsider...
• Actually, let me recalculate this step:
• 'd' > 'b' and last['d'] = 4 which is NOT > 6, so we cannot pop 'd'
• Add 'b' after 'd'
• stack = ['a', 'c', 'd', 'b'], visited = {'a', 'c', 'd', 'b'}

Index 7: c = 'c'

• 'c' already in visited, skip

Final Result: "acdb"

The key insight: When we encountered 'b' at index 6, we couldn't remove 'd' even though 'd' > 'b', because 'd' wouldn't appear again later. This demonstrates why tracking the last occurrence is crucial - we can only remove characters if we're guaranteed to see them again.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s.

• Creating the last dictionary takes O(n) time as we iterate through the string once
• The main loop iterates through each character in the string once, which is O(n)
• Although there's a nested while loop, each character can be pushed to and popped from the stack at most once throughout the entire execution
• The in operation for checking vis (a set) is O(1)
• The remove operation from vis is also O(1) for a set
• Therefore, the total time complexity is O(n) + O(n) = O(n)

Space Complexity: O(n), where n is the length of the string s.

• The last dictionary stores at most 26 entries (for lowercase English letters), but in the worst case with unique characters, it could store up to n entries, so it's O(n)
• The stk list can contain at most 26 unique characters (or n in the worst case), which is O(n)
• The vis set similarly stores at most 26 characters (or n in the worst case), which is O(n)
• The output string construction takes O(n) space
• Therefore, the total space complexity is O(n)

Common Pitfalls

Pitfall 1: Forgetting to Check if Character Appears Later

The Mistake: A common error is popping characters from the stack without verifying they appear later in the string:

# WRONG - This removes characters even if they won't appear again
while stack and stack[-1] > char:
    removed_char = stack.pop()
    visited.remove(removed_char)

Why It's Wrong: If we remove a character that doesn't appear later, we lose it permanently from our result, violating the requirement that every unique character must appear in the final string.

Example: For s = "dbca":

• When we encounter 'a', if we pop 'c' without checking, we lose 'c' forever
• Result would be "dba" instead of the correct "dbca"

The Fix: Always check last_occurrence[stack[-1]] > index before popping:

# CORRECT - Only remove if the character appears again later
while stack and stack[-1] > char and last_occurrence[stack[-1]] > index:
    removed_char = stack.pop()
    visited.remove(removed_char)

Pitfall 2: Not Tracking Visited Characters Properly

The Mistake: Forgetting to maintain the visited set or not updating it correctly when popping:

# WRONG - Forgetting to update visited when popping
while stack and stack[-1] > char and last_occurrence[stack[-1]] > index:
    stack.pop()  # Forgot to remove from visited set!

Why It's Wrong: The visited set prevents duplicate processing. If we don't remove popped characters from visited, the algorithm will skip them when they appear again, even though they're no longer in the stack.

Example: For s = "bcabc":

• After popping 'b' at index 2, if 'b' remains in visited
• When we encounter 'b' again at index 3, we'll skip it
• Result would be incomplete

The Fix: Always synchronize the visited set with stack operations:

# CORRECT - Keep visited set synchronized with stack
while stack and stack[-1] > char and last_occurrence[stack[-1]] > index:
    removed_char = stack.pop()
    visited.remove(removed_char)  # Must remove from visited

Pitfall 3: Using Wrong Comparison for Lexicographical Order

The Mistake: Comparing indices instead of characters:

# WRONG - Comparing indices instead of characters
while stack and index < last_occurrence[stack[-1]] and last_occurrence[stack[-1]] > index:
    # This doesn't ensure lexicographical order

Why It's Wrong: Lexicographical order depends on character values ('a' < 'b' < 'c'...), not their positions in the string.

The Fix: Compare characters directly using stack[-1] > char:

# CORRECT - Compare characters for lexicographical order
while stack and stack[-1] > char and last_occurrence[stack[-1]] > index:

Pitfall 4: Processing Duplicates Multiple Times

The Mistake: Not checking if a character is already in the result before processing:

# WRONG - Processing every character without checking
for index, char in enumerate(s):
    # Missing the check: if char in visited: continue
    while stack and stack[-1] > char and last_occurrence[stack[-1]] > index:
        removed_char = stack.pop()
        visited.remove(removed_char)
    stack.append(char)  # This could add duplicates!
    visited.add(char)

Why It's Wrong: Without the skip check, we might try to add a character that's already in our result, potentially causing incorrect popping of other characters or adding duplicates.

The Fix: Always check if the character is already visited before processing:

# CORRECT - Skip characters already in the result
if char in visited:
    continue