MediumHash TableStringStackGreedyUpdated Sep 2026

2434. Using a Robot to Print the Lexicographically Smallest String

Asked at Rippling, Visa

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Hash Table

Companies

2

Problem

You start with a string s and an empty stack t. You also have a piece of paper, which starts empty. You repeat these two moves until both s and t are empty:

  1. Take the first character of s and push it onto the top of t.
  2. Take the top character of t and write it on the paper (this removes it from t).

Return the lexicographically smallest string you can write on the paper. Lexicographically smallest means: compare strings character by character; the one with the smaller character at the first place where they differ is smaller.

You may mix the two moves in any order you like. The only limits are that you can only read s from the front, and you can only write from the top of the stack t.

Two moves, one output

szza012frontYou can only take the first character of s.tzza← topThe top of t (orange) is the only character you canwrite.paperazz012Popping t in order gives the smallest result here:"azz".
Read characters from the front of s onto the stack t, and write characters from the top of t onto the paper.

Constraints

  • ●1 <= s.length <= 10^5
  • ●s consists of only English lowercase letters

Examples

Example 1
Inputs = "zza"
Output"azz"
WhyPush all three characters ('z','z','a') onto the stack, then pop them all. The stack pops in reverse order, giving 'a','z','z' = "azz". Printing earlier would put a 'z' first, which is worse.
Example 2
Inputs = "bac"
Output"abc"
WhyPush 'b' and 'a' (stack is b,a). Pop twice to write "ab". Then push 'c' and pop it to write "abc". Writing 'b' before 'a' would give a larger first character.
Example 3
Inputs = "bdda"
Output"addb"
WhyPush all four characters, then pop them all. The stack pops in reverse: 'a','d','d','b' = "addb". Any earlier pop would start with 'b' or 'd', which is bigger than 'a'.

Asked At

2 companies
CompanyDifficulty
RipplingMediumView all Rippling questions →
VisaMediumView all Visa questions →

How to Think About It

1

Precompute the minimum character from each position to the end of t

2

Use a stack to hold characters that have been read but not yet printed

3

Greedy: print from the stack only when the top is smaller than or equal to the upcoming minimum

4

Pop and print all characters from the stack that are smaller than the current minimum

5

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.

Greedy with suffix minimum

szza012Suffix minimum from each index: [a, a, a]. Thesmallest remaining character is 'a'.tzza← topAfter pushing all of s, the top 'a' <= suffix min 'a',so we pop it.tzz← topNow the suffix is empty, so we just pop the rest: 'z'then 'z'.pop while top <= min(s[i:])else keep pushing
Push each character, then pop while the top is no larger than the smallest character still left in s.
ComplexityTime O(n)Space O(n)We scan the string once to build the suffix-minimum array and once to push/pop each character at most once, so the work is linear in the length of s.

What Trips People Up in Real Interviews

1

Clarify the exact mechanics: read one char at a time, push or print

2

Ask if the stack can hold only one character (typically yes for this variant)

3

Explain the greedy invariant: print from stack when top <= min of remaining

4

Discuss why printing earlier when possible yields the lexicographically smallest result

5

Mention the time complexity is O(n) using precomputed suffix minimums

Solution Code

O(n) time
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)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

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 runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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, Visa. 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