Skip to main content
Talentd

Using a Robot to Print the Lexicographically Smallest String - Solution & Explanation

MediumHash TableStringStackGreedy14 min readAsked at: Amazon, Meta, Salesforce +3
Practice this problem

Problem Statement

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:

  • Remove the first character of a string s and give it to the robot. The robot will append this character to the string t.
  • Remove the last character of a string 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 <= 105
  • s consists of only English lowercase letters.

Approach Overview

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.

Approach 1: Greedy Approach with Two Stacks

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Character Frequency and Priority Queue

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Greedy + Stack

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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 t_stack and min_suffix requiring linear space.

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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Stack and Remaining MinimumO(n)O(n)Best general solution; optimal for interviews and large inputs
Character Frequency + Priority QueueO(n log k)O(n)Useful when you want explicit tracking of the smallest remaining character

Video Solution

Using a Robot to Print the Lexicographically Smallest String | Thought Process | Leetcode 2434 | MIK • codestorywithMIK • 11,803 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Using a Robot to Print the Lexicographically Smallest String easy or hard?
The problem is rated Medium because the robot operations are simple but the greedy insight is not immediately obvious. Once you recognize that you must compare the stack top with the smallest remaining character, the implementation becomes straightforward and runs in linear time.
Using a Robot to Print the Lexicographically Smallest String Python/Java solution
Most implementations use the greedy stack method. Python and C++ typically track remaining characters with a 26‑length frequency array, while Java or JavaScript versions sometimes use a priority queue. All versions follow the same idea: push characters, then pop when the stack top is safe to output.
How to solve Using a Robot to Print the Lexicographically Smallest String in O(n)?
Track the frequency of remaining characters while scanning the string. Push characters onto a stack and update the smallest remaining character. While the stack top is less than or equal to that smallest character, pop it and append it to the result. Because each character is pushed and popped once, the algorithm runs in O(n) time.
What is the best approach for Using a Robot to Print the Lexicographically Smallest String?
The optimal approach uses a greedy strategy with a stack and a frequency array to track the smallest remaining character. Iterate through the string, push characters to a stack, and pop them when the stack top is smaller than or equal to the smallest remaining character. Each character is processed at most twice, giving O(n) time and O(n) space complexity.
Is Using a Robot to Print the Lexicographically Smallest String asked at Google/Amazon/Meta?
This problem reflects common interview themes at companies like Google, Amazon, and Meta: greedy decision making, stack simulation, and lexicographical ordering. Variants of stack‑based greedy string construction appear frequently in technical interviews.
What data structure is used in Using a Robot to Print the Lexicographically Smallest String?
The core data structure is a stack that simulates the robot's temporary storage. A frequency array or priority queue tracks the smallest remaining character in the unread portion of the string. Together they enable greedy decisions about when to print characters.
What is the time complexity of Using a Robot to Print the Lexicographically Smallest String?
The optimal greedy stack solution runs in O(n) time where n is the length of the string. Each character is pushed to the stack once and popped at most once. The space complexity is O(n) for the stack and result string, plus O(1) for a 26‑character frequency array.

Ready to solve this problem?

Practice Using a Robot to Print the Lexicographically Smallest String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Permutation