Using a Robot to Print the Lexicographically Smallest String - Video Solutions

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.