Using a Robot to Print the Lexicographically Smallest String
Asked at Rippling
Problem
Given a string t, a robot can read characters from t one at a time and either push them onto a stack or print them immediately. The stack has a capacity of one character at a time (you can print the top of the stack). Find the lexicographically smallest string that can be printed by optimally deciding when to push and when to print.
Asked At
| Company | Difficulty | |
|---|---|---|
| Rippling | MEDIUM | View all Rippling questions → |
How to Think About It
Precompute the minimum character from each position to the end of t
Use a stack to hold characters that have been read but not yet printed
Greedy: print from the stack only when the top is smaller than or equal to the upcoming minimum
Pop and print all characters from the stack that are smaller than the current minimum
The key insight is comparing the stack top against the minimum remaining character in t
Optimal Approach
Precompute the minimum character from each index to the end of the string t. Iterate through t: for each character, push it onto the stack. Then, while the stack is not empty and the top of the stack is less than or equal to the minimum character in the remaining string, pop and append it to the result. This greedy approach ensures we print the smallest possible character as early as possible. The suffix minimum array tells us whether there is still a smaller character ahead, preventing us from printing too early.
What Trips People Up in Real Interviews
Clarify the exact mechanics: read one char at a time, push or print
Ask if the stack can hold only one character (typically yes for this variant)
Explain the greedy invariant: print from stack when top <= min of remaining
Discuss why printing earlier when possible yields the lexicographically smallest result
Mention the time complexity is O(n) using precomputed suffix minimums
Solution Code
class Solution:
def robotWithString(self, t: str) -> str:
n = len(t)
min_suffix = [''] * n
min_suffix[-1] = t[-1]
for i in range(n - 2, -1, -1):
min_suffix[i] = min(t[i], min_suffix[i + 1])
stack = []
result = []
for i, ch in enumerate(t):
stack.append(ch)
while stack and stack[-1] <= min_suffix[i]:
result.append(stack.pop())
while stack:
result.append(stack.pop())
return ''.join(result)Frequently Asked Questions
What is the Using a Robot to Print the Lexicographically Smallest String problem?
Given a string t, a robot can read characters from t one at a time and either push them onto a stack or print them immediately. The stack has a capacity of one character at a time (you can print the top of the stack). Find the lexicographically smallest string that can be printed by optimally deciding when to push and when to print.
How do you solve Using a Robot to Print the Lexicographically Smallest String?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Using a Robot to Print the Lexicographically Smallest String?
Using a Robot to Print the Lexicographically Smallest String is asked at Rippling. It is a medium difficulty problem.
What are common mistakes on Using a Robot to Print the Lexicographically Smallest String?
- Clarify the exact mechanics: read one char at a time, push or print
- Ask if the stack can hold only one character (typically yes for this variant)
- Explain the greedy invariant: print from stack when top <= min of remaining
- Discuss why printing earlier when possible yields the lexicographically smallest result
- Mention the time complexity is O(n) using precomputed suffix minimums