LeetCode 2434 - Using a Robot to Print the Lexicographically Smallest String
In this problem, we are given a string s and a robot that manages another temporary string t. Initially, t is empty. The robot repeatedly performs one of two allowed operations: First, it may remove the first character from s and append it to the end of t.
Difficulty: 🟡 Medium
Topics: Hash Table, String, Stack, Greedy
Solution
Problem Understanding
In this problem, we are given a string s and a robot that manages another temporary string t. Initially, t is empty. The robot repeatedly performs one of two allowed operations:
First, it may remove the first character from s and append it to the end of t.
Second, it may remove the last character from t and append it to the final output string, which is the string written on paper.
The goal is to determine the lexicographically smallest possible output string that can be produced after both s and t become empty.
The important detail is that t behaves exactly like a stack. Characters are pushed into t from the front of s, and popped from the end of t onto the result. Because of this, we cannot arbitrarily reorder characters. We can only delay writing characters by keeping them inside the stack.
Lexicographical order works the same way as dictionary order. A string is smaller if, at the first position where the two strings differ, it contains the smaller character. For example:
"abc"is smaller than"acb""addb"is smaller than"bdda"
The constraints allow strings of length up to 10^5, so any solution that explores many possible operation sequences will be far too slow. We need an efficient greedy strategy that decides exactly when characters should be written to the answer.
Several edge cases are important:
- Strings that are already sorted, like
"abc" - Strings in reverse order, like
"cba" - Strings containing many duplicate letters
- Strings where the smallest character appears late
- Strings with only one character
The problem guarantees that all characters are lowercase English letters, which is extremely useful because there are only 26 possible character values.
Approaches
Brute Force Approach
A brute force solution would try every valid sequence of operations. At each step, if s is non-empty, we may move a character from s into t. If t is non-empty, we may pop from t into the answer.
This creates a huge decision tree. Different operation orders produce different outputs, and we would need to compare all generated strings to find the smallest one.
The brute force approach is correct because it exhaustively explores every valid sequence of operations. However, it quickly becomes infeasible. The number of possible operation sequences grows exponentially with the string length.
For n = 10^5, this approach is completely impossible.
Key Insight
The crucial observation is that we should write characters as early as possible, but only when doing so cannot hurt the lexicographical order.
Suppose the top of the stack t contains character 'c'. We should pop it immediately if there is no smaller character remaining somewhere in the unread part of s.
Why?
Because delaying 'c' would only place it later in the result string. If no smaller future character exists, then writing 'c' now is always optimal.
This suggests a greedy strategy:
- Process characters from left to right
- Push characters into a stack
- Track the smallest remaining character still present in the unread suffix
- While the stack top is less than or equal to that smallest remaining character, pop it into the result
To efficiently know the smallest remaining character, we maintain a frequency count of characters still left in s.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n) or worse | O(n) | Explores all valid operation sequences |
| Optimal | O(n) | O(n) | Greedy stack with remaining character tracking |
Algorithm Walkthrough
- Create a frequency array of size 26 to count how many times each character appears in
s. - Initialize an empty stack
t. This represents the robot's temporary storage. - Initialize an empty list
resultto build the final answer efficiently. - Iterate through each character in
s. - Push the current character onto the stack because the only way to access future characters is to move through the string sequentially.
- Decrease the frequency count for the current character because it is no longer part of the unread suffix.
- Determine the smallest character that still exists in the remaining unread portion of
s. We do this by scanning the frequency array from'a'to'z'. - While the stack is not empty, check whether the top character can safely be written to the result.
- If the stack top is less than or equal to the smallest remaining character, pop it from the stack and append it to the result. This is greedy because placing a smaller or equal character earlier always improves or preserves lexicographical order.
- Otherwise, stop popping. A smaller future character still exists, so we should wait.
- After processing all characters in
s, pop every remaining character from the stack into the result. - Join the result list into a string and return it.
Why it works
The invariant is that we only delay characters when a strictly smaller character still exists in the unread suffix. If no smaller future character exists, then keeping the current character in the stack can never improve the lexicographical order.
Therefore, every pop operation is greedily optimal at the moment it occurs. Since lexicographical order depends on earlier positions first, always writing the smallest possible available character produces the globally optimal answer.
Python Solution
class Solution:
def robotWithString(self, s: str) -> str:
remaining = [0] * 26
for ch in s:
remaining[ord(ch) - ord('a')] += 1
stack = []
result = []
smallest_index = 0
for ch in s:
stack.append(ch)
idx = ord(ch) - ord('a')
remaining[idx] -= 1
while smallest_index < 26 and remaining[smallest_index] == 0:
smallest_index += 1
while stack:
top_index = ord(stack[-1]) - ord('a')
if smallest_index == 26 or top_index <= smallest_index:
result.append(stack.pop())
else:
break
return "".join(result)
The implementation begins by counting how many times each character appears in the string. This allows us to know which characters still remain unread.
The stack variable simulates the robot's temporary string t. Characters are pushed into it as we process the input.
The smallest_index pointer tracks the lexicographically smallest character still remaining in the unread suffix. Instead of rescanning all 26 characters repeatedly from the beginning, we advance this pointer only when a character count becomes zero.
For each character:
- We push it into the stack
- Remove it from the remaining frequency count
- Update the smallest remaining character
- Pop from the stack while it is safe to do so
The condition:
top_index <= smallest_index
means the current stack top is not larger than any future character. Therefore, writing it now is optimal.
Finally, the result list is joined into the final string.
Go Solution
func robotWithString(s string) string {
remaining := make([]int, 26)
for _, ch := range s {
remaining[ch-'a']++
}
stack := make([]byte, 0)
result := make([]byte, 0)
smallestIndex := 0
for i := 0; i < len(s); i++ {
ch := s[i]
stack = append(stack, ch)
remaining[ch-'a']--
for smallestIndex < 26 && remaining[smallestIndex] == 0 {
smallestIndex++
}
for len(stack) > 0 {
top := stack[len(stack)-1]
topIndex := int(top - 'a')
if smallestIndex == 26 || topIndex <= smallestIndex {
result = append(result, top)
stack = stack[:len(stack)-1]
} else {
break
}
}
}
return string(result)
}
The Go implementation follows exactly the same logic as the Python version.
Slices are used for both the stack and the result builder. Popping from the stack is handled by reslicing:
stack = stack[:len(stack)-1]
Since the input contains only lowercase English letters, integer overflow is not a concern. The algorithm also avoids unnecessary string concatenation by building the answer with a byte slice.
Worked Examples
Example 1
Input:
s = "zza"
Initial frequency counts:
z: 2
a: 1
| Step | Current Char | Stack | Smallest Remaining | Result |
|---|---|---|---|---|
| 1 | z | [z] | a | "" |
| 2 | z | [z,z] | a | "" |
| 3 | a | [z,z,a] | none | "" |
Now no characters remain unread, so we pop everything:
| Action | Stack | Result |
|---|---|---|
| pop a | [z,z] | "a" |
| pop z | [z] | "az" |
| pop z | [] | "azz" |
Final answer:
"azz"
Example 2
Input:
s = "bac"
| Step | Current Char | Stack | Smallest Remaining | Result |
|---|---|---|---|---|
| 1 | b | [b] | a | "" |
| 2 | a | [b,a] | c | "" |
Now the stack top is a, and a <= c, so pop:
| Action | Stack | Result |
|---|---|---|
| pop a | [b] | "a" |
| pop b | [] | "ab" |
Continue processing:
| Step | Current Char | Stack | Smallest Remaining | Result |
|---|---|---|---|---|
| 3 | c | [c] | none | "ab" |
Pop remaining:
| Action | Stack | Result |
|---|---|---|
| pop c | [] | "abc" |
Final answer:
"abc"
Example 3
Input:
s = "bdda"
| Step | Current Char | Stack | Smallest Remaining | Result |
|---|---|---|---|---|
| 1 | b | [b] | a | "" |
| 2 | d | [b,d] | a | "" |
| 3 | d | [b,d,d] | a | "" |
| 4 | a | [b,d,d,a] | none | "" |
Now pop everything:
| Action | Stack | Result |
|---|---|---|
| pop a | [b,d,d] | "a" |
| pop d | [b,d] | "ad" |
| pop d | [b] | "add" |
| pop b | [] | "addb" |
Final answer:
"addb"
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each character is pushed and popped at most once |
| Space | O(n) | The stack and result may store all characters |
The frequency array has constant size 26, so its cost is negligible. Every character enters the stack exactly once and leaves exactly once, giving linear time overall.
Test Cases
sol = Solution()
assert sol.robotWithString("zza") == "azz" # Example 1
assert sol.robotWithString("bac") == "abc" # Example 2
assert sol.robotWithString("bdda") == "addb" # Example 3
assert sol.robotWithString("a") == "a" # Single character
assert sol.robotWithString("aaaa") == "aaaa" # All identical characters
assert sol.robotWithString("abc") == "abc" # Already sorted
assert sol.robotWithString("cba") == "abc" # Reverse sorted
assert sol.robotWithString("leetcode") == "cdeoteel" # Mixed ordering
assert sol.robotWithString("bydizfve") == "bdevfziy" # Complex ordering
assert sol.robotWithString("zzzzza") == "azzzzz" # Smallest char at end
assert sol.robotWithString("abab") == "aabb" # Alternating pattern
assert sol.robotWithString("edcba") == "abcde" # Strict descending
Test Summary
| Test | Why |
|---|---|
"zza" |
Verifies delayed popping |
"bac" |
Verifies interleaving push and pop operations |
"bdda" |
Verifies stack reversal behavior |
"a" |
Smallest possible input |
"aaaa" |
Handles duplicate characters |
"abc" |
Already optimal ordering |
"cba" |
Reverse ordering stress case |
"leetcode" |
Realistic mixed input |
"bydizfve" |
Complex greedy interactions |
"zzzzza" |
Smallest character appears last |
"abab" |
Alternating repeated pattern |
"edcba" |
Forces maximum stack buildup |
Edge Cases
One important edge case is when the input contains only one character. In this situation, the stack receives exactly one push and one pop. Some implementations accidentally mishandle empty stack conditions after popping. This implementation safely handles the case because all stack operations are guarded by while stack: checks.
Another important case is when the smallest character appears very late in the string, such as "zzzzza". A naive greedy algorithm might incorrectly pop early 'z' characters too soon. Our implementation correctly delays popping because the remaining suffix still contains 'a', which is smaller than 'z'.
A third tricky case is repeated identical characters, such as "aaaa". Some solutions incorrectly use strict comparison instead of non-strict comparison when deciding whether to pop. The condition:
top_index <= smallest_index
is essential. Equal characters should also be popped immediately because delaying them cannot improve lexicographical order.
Another subtle case is reverse sorted input like "edcba". Here, every character must remain in the stack until the very end. The implementation handles this naturally because a smaller future character always exists until the final step.