Problem Description

You have a string s and a robot that holds an empty string t. The robot can perform two operations repeatedly until both strings are empty:

1. Operation 1: Take the first character from string s and append it to the end of string t
2. Operation 2: Take the last character from string t and write it on paper (removing it from t)

Your goal is to determine the lexicographically smallest string that can be written on the paper by choosing the operations strategically.

The process works like this:

• String s acts as an input queue where you can only remove from the front
• String t acts as a stack where the robot can append characters to the end (from s) or remove from the end (to write on paper)
• Characters written on paper form the final result string in the order they are written

For example, if s = "bac":

• You could take 'b' from s to t (now t = "b", s = "ac")
• Take 'a' from s to t (now t = "ba", s = "c")
• Write 'a' from t to paper (now t = "b", paper has "a")
• Write 'b' from t to paper (now t = "", paper has "ab")
• Take 'c' from s to t (now t = "c", s = "")
• Write 'c' from t to paper (final result: "abc")

The challenge is to find the optimal sequence of operations that produces the lexicographically smallest possible result string.

Intuition

The key insight is that string t acts like a stack, and we want to write characters to paper in lexicographically smallest order. To achieve this, we should write a character from t to paper when it's advantageous to do so.

When should we write a character from t to paper? We should write it when:

• The character at the top of t is smaller than or equal to any character we could potentially get from s in the future

This is because if we wait and take more characters from s first, we might end up having to write larger characters before we can access the smaller one that's currently at the top of t.

To make this decision, we need to know what's the smallest character remaining in s at any point. If the top of our stack t has a character that's less than or equal to the smallest remaining character in s, we should write it immediately. This ensures we're always writing the smallest possible character at each step.

For example, if t has 'b' at the top and the smallest remaining character in s is 'c', we should write 'b' now. If we don't, we'd have to stack 'c' on top of 'b', and then we'd be forced to write 'c' before 'b', resulting in a lexicographically larger string.

The strategy becomes:

1. Keep track of the count of each character remaining in s
2. Maintain the current minimum character that hasn't been exhausted in s
3. For each character we take from s, push it to the stack t
4. After pushing, check if the top of the stack is less than or equal to the minimum remaining character - if so, pop and write it
5. Keep popping and writing as long as this condition holds

This greedy approach ensures that at each step, we're making the locally optimal choice that leads to the globally optimal (lexicographically smallest) result.

Learn more about Stack and Greedy patterns.

Solution Approach

The implementation uses a greedy approach with a stack to build the lexicographically smallest result string.

Data Structures Used:

• cnt: A Counter (frequency map) to track the count of each character remaining in string s
• stk: A list acting as a stack to represent the robot's string t
• ans: A list to collect characters written to paper
• mi: A variable tracking the smallest character that still exists in the unprocessed part of s

Algorithm Steps:

1. Initialize the frequency counter: Create cnt = Counter(s) to know how many of each character we have in total.

2. Set initial minimum: Start with mi = 'a' as the smallest possible character.

3. Process each character in s:

   • Decrement the count: cnt[c] -= 1 (we're removing this character from the remaining pool)
   • Update the minimum character: While the current mi has count 0, increment it to the next character

     while mi < 'z' and cnt[mi] == 0:
         mi = chr(ord(mi) + 1)

   • Push the current character onto the stack: stk.append(c)
   • Pop and write characters when beneficial: While the stack is not empty and its top element is less than or equal to mi, pop it and add to the answer

     while stk and stk[-1] <= mi:
         ans.append(stk.pop())

4. Return the result: Join all characters in ans to form the final string.

Why this works:

The critical insight is in the condition stk[-1] <= mi. When the top of the stack is less than or equal to the smallest remaining character in s, we should write it immediately. This is because:

• If stk[-1] < mi: Writing it now gives us a smaller character in our result than any future character from s
• If stk[-1] == mi: Writing it now is at least as good as waiting, and it might allow us to access even smaller characters buried deeper in the stack

By continuously updating mi and making greedy decisions to pop from the stack whenever possible, we ensure that we're always writing the smallest available character at each position, resulting in the lexicographically smallest final string.

Example Walkthrough

Let's trace through the algorithm with s = "bdbc".

Initial Setup:

• cnt = {'b': 2, 'd': 1, 'c': 1} (frequency of each character)
• stk = [] (empty stack)
• ans = [] (empty result)
• mi = 'a' (starting minimum)

Step 1: Process 'b' (index 0)

• cnt['b'] -= 1 → cnt = {'b': 1, 'd': 1, 'c': 1}
• Update mi: 'a' has count 0, so increment → mi = 'b'
• Push 'b' to stack → stk = ['b']
• Check if we should pop: Is 'b' ≤ 'b'? Yes! Pop 'b' and write it → ans = ['b'], stk = []

Step 2: Process 'd' (index 1)

• cnt['d'] -= 1 → cnt = {'b': 1, 'd': 0, 'c': 1}
• Update mi: 'b' still has count 1, so mi = 'b'
• Push 'd' to stack → stk = ['d']
• Check if we should pop: Is 'd' ≤ 'b'? No! Keep 'd' in stack

Step 3: Process 'b' (index 2)

• cnt['b'] -= 1 → cnt = {'b': 0, 'd': 0, 'c': 1}
• Update mi: 'b' now has count 0, increment → mi = 'c'
• Push 'b' to stack → stk = ['d', 'b']
• Check if we should pop: Is 'b' ≤ 'c'? Yes! Pop 'b' → ans = ['b', 'b'], stk = ['d']
• Continue checking: Is 'd' ≤ 'c'? No! Stop popping

Step 4: Process 'c' (index 3)

• cnt['c'] -= 1 → cnt = {'b': 0, 'd': 0, 'c': 0}
• Update mi: All counts are 0, mi becomes 'z' (no more characters)
• Push 'c' to stack → stk = ['d', 'c']
• Check if we should pop: Is 'c' ≤ 'z'? Yes! Pop 'c' → ans = ['b', 'b', 'c'], stk = ['d']
• Continue checking: Is 'd' ≤ 'z'? Yes! Pop 'd' → ans = ['b', 'b', 'c', 'd'], stk = []

Final Result: "bbcd"

The key decisions were:

• Writing 'b' immediately when we first saw it (since 'b' was the minimum remaining)
• Holding 'd' in the stack when we knew a 'b' was still coming
• Writing the second 'b' before 'd' to maintain lexicographic order
• Finally writing 'c' and 'd' in that order

This gives us the lexicographically smallest possible result "bbcd" instead of alternatives like "bdbc" or "dbbc".

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + |Σ|) where n is the length of string s and |Σ| is the size of the character set (26 for lowercase English letters).

• Creating the Counter takes O(n) time to count all characters in the string
• The main loop iterates through each character in s once, which is O(n)
• Inside the main loop:
  • Decrementing the counter: O(1)
  • Finding the next minimum character: The inner while loop advances mi from 'a' to 'z' at most once throughout the entire execution, not per iteration. This contributes O(26) = O(|Σ|) total
  • Appending to stack: O(1)
  • The inner while loop for popping from stack: Each element is pushed once and popped at most once, contributing O(n) total across all iterations
• Joining the answer list: O(n)

Total: O(n) + O(n) + O(|Σ|) + O(n) = O(n + |Σ|)

Space Complexity: O(n)

• Counter storage: O(|Σ|) = O(26) = O(1) for storing counts of at most 26 distinct characters
• Answer list ans: Can contain up to n characters, so O(n)
• Stack stk: Can contain up to n characters in the worst case, so O(n)
• Variable mi: O(1)

Total: O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Minimum Character Update Logic

The Problem: A common mistake is updating the minimum remaining character (min_remaining_char) at the wrong time or incorrectly. Some implementations might:

• Update it before decrementing the count, causing off-by-one errors
• Forget to update it at all after processing a character
• Use incorrect bounds checking (forgetting the < 'z' condition)

Incorrect Example:

# WRONG: Updating before decrementing count
for current_char in s:
    while min_remaining_char < 'z' and char_count[min_remaining_char] == 0:
        min_remaining_char = chr(ord(min_remaining_char) + 1)
    char_count[current_char] -= 1  # This should come first!
    stack.append(current_char)
    # ...

Solution: Always decrement the count first, then update the minimum:

for current_char in s:
    char_count[current_char] -= 1  # Decrement first
    while min_remaining_char < 'z' and char_count[min_remaining_char] == 0:
        min_remaining_char = chr(ord(min_remaining_char) + 1)
    # ...

Pitfall 2: Forgetting to Empty the Stack After Processing

The Problem: After processing all characters from string s, there might still be characters left in the stack. The algorithm shown correctly handles this by using <= in the comparison, which naturally empties the stack at the end. However, some implementations might use < instead or have additional logic that prevents complete stack emptying.

Incorrect Example:

# WRONG: Using strict less than
while stack and stack[-1] < min_remaining_char:  # Should be <=
    result.append(stack.pop())

This would leave characters in the stack when min_remaining_char reaches 'z' or beyond.

Solution: Use <= comparison or explicitly empty the stack after the main loop:

# Option 1: Use <= (as in the correct solution)
while stack and stack[-1] <= min_remaining_char:
    result.append(stack.pop())

# Option 2: Explicitly empty stack after main loop
for current_char in s:
    # ... main processing ...
  
# Empty any remaining characters
while stack:
    result.append(stack.pop())

Pitfall 3: Misunderstanding the Greedy Strategy

The Problem: Some might think we should always pop characters immediately if they're small, without considering what's coming next. This leads to incorrect logic like popping whenever we see a character smaller than the current one.

Incorrect Example:

# WRONG: Popping based on current character instead of minimum remaining
for current_char in s:
    stack.append(current_char)
    while stack and stack[-1] <= current_char:  # Wrong comparison!
        result.append(stack.pop())

Solution: The key insight is comparing against the minimum character still available in the unprocessed part of s, not the current character. This ensures we make globally optimal decisions rather than locally greedy ones.

# Correct: Compare against minimum remaining character
while stack and stack[-1] <= min_remaining_char:
    result.append(stack.pop())