You are given a string s and a robot that currently holds an empty string t. Apply one of the following operations until s and t are both empty:
s and give it to the robot. The robot will append this character to the string t.t and give it to the robot. The robot will write this character on paper.Return the lexicographically smallest string that can be written on the paper.
Example 1:
Input: s = "zza" Output: "azz" Explanation: Let p denote the written string. Initially p="", s="zza", t="". Perform first operation three times p="", s="", t="zza". Perform second operation three times p="azz", s="", t="".
Example 2:
Input: s = "bac" Output: "abc" Explanation: Let p denote the written string. Perform first operation twice p="", s="c", t="ba". Perform second operation twice p="ab", s="c", t="". Perform first operation p="ab", s="", t="c". Perform second operation p="abc", s="", t="".
Example 3:
Input: s = "bdda" Output: "addb" Explanation: Let p denote the written string. Initially p="", s="bdda", t="". Perform first operation four times p="", s="", t="bdda". Perform second operation four times p="addb", s="", t="".
Constraints:
1 <= s.length <= 105s consists of only English lowercase letters.Problem Overview: You receive a string s. A robot reads characters from left to right and can either push them to a stack or pop from the stack to print them. The goal is to control these operations so the final printed string is the lexicographically smallest possible.
Approach 1: Greedy with Stack and Remaining Minimum Tracking (O(n) time, O(n) space)
The key observation is that you should delay printing larger characters if a smaller character still appears later in the string. Iterate through s, pushing each character onto a stack. Track the smallest character that still remains to the right using a frequency array. After each push, pop from the stack while the top character is less than or equal to the smallest remaining character and append it to the result. This works because printing the smallest available character earlier guarantees a lexicographically smaller prefix. The stack ensures characters are released in the correct order while respecting the robot’s operations. This approach relies heavily on a stack and a greedy decision rule.
Approach 2: Character Frequency with Priority Queue (O(n log k) time, O(n) space)
Another way to reason about the problem is to always know the smallest character still available in the unread portion of the string. Maintain a frequency map for remaining characters and use a min priority queue to track the smallest character that can appear next. As you iterate through the input string, push characters onto a stack. After updating frequencies, compare the stack’s top with the smallest character in the priority queue. If the stack top is smaller or equal, pop it and append to the result. Otherwise continue reading characters. The heap helps quickly determine the next smallest remaining character while the stack simulates the robot buffer.
Recommended for interviews: The greedy stack solution is the expected answer. It runs in O(n) time because each character is pushed and popped at most once, and the smallest remaining character can be tracked using a simple frequency array of size 26. Interviewers like this solution because it shows understanding of greedy ordering and efficient stack simulation. The priority queue variant is easier to reason about conceptually but introduces an unnecessary log k factor and more overhead.
The key idea is to use two stacks to simulate the operations. First, iterate through the string s and push each character onto a stack representing t. Also maintain an additional stack that represents the minimum character that can still be taken from s at each point. This helps in deciding when to pop a character from t to the final result string.
At each step, compare the last character of t with the smallest character that can be taken from s. This ensures that characters are added in lexicographical order.
This Python code uses the concept of a stack to simulate the robot operation. A list t_stack simulates the robot's temporary storage, and result accumulates the final string. A helper list min_suffix keeps track of the smallest character from each position to the end of string s. This enables comparisons and decision-making for moving characters.
Time Complexity: O(n) where n is the length of string s, as each operation (push/pop/compare) is O(1) and every character is processed once.
Space Complexity: O(n) due to both t_stack and min_suffix requiring linear space.
In this approach, a priority queue can be used to determine the smallest character that can be popped from either s or t. By maintaining character frequency, this approach can selectively remove characters to ensure the smallest lexicographical order at each step.
This Java code leverages a stack to simulate the process of transferring characters, along with an array to track character frequencies. The loop checks if the smallest character from the priority queue is in tStack or the remaining s to make decisions on which character to move to the resulting string.
Java
JavaScript
Time Complexity: O(n), as each character operation is iterated over a constant number of possibilities.
Space Complexity: O(n) due to the stack and character count arrays.
The problem can be transformed into: given a string sequence, use an auxiliary stack to convert it into the lexicographically smallest string sequence.
We can use an array cnt to maintain the count of each character in string s, use a stack stk as the auxiliary stack mentioned in the problem, and use a variable mi to keep track of the smallest character not yet traversed in the string.
Traverse the string s. For each character c, first decrement its count in the array cnt and update mi. Then push c onto the stack. At this point, if the top element of the stack is less than or equal to mi, repeatedly pop the top element from the stack and add it to the answer.
After the traversal, return the answer.
The time complexity is O(n + |\Sigma|), and the space complexity is O(n), where n is the length of the string s and |\Sigma| is the size of the character set, which is 26 in this problem.
| Approach | Complexity |
|---|---|
| Greedy Approach with Two Stacks | Time Complexity: O(n) where n is the length of string s, as each operation (push/pop/compare) is O(1) and every character is processed once. Space Complexity: O(n) due to both |
| Character Frequency and Priority Queue | Time Complexity: O(n), as each character operation is iterated over a constant number of possibilities. Space Complexity: O(n) due to the stack and character count arrays. |
| Greedy + Stack | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Stack and Remaining Minimum | O(n) | O(n) | Best general solution; optimal for interviews and large inputs |
| Character Frequency + Priority Queue | O(n log k) | O(n) | Useful when you want explicit tracking of the smallest remaining character |
Using a Robot to Print the Lexicographically Smallest String | Thought Process | Leetcode 2434 | MIK • codestorywithMIK • 11,502 views views
Watch 9 more video solutions →Practice Using a Robot to Print the Lexicographically Smallest String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor