Reorder a string using a robot that can hold characters in a stack-like buffer, and output the lexicographically smallest possible result.
Using a Robot to Print the Lexicographically Smallest String
You are given a string s. A robot processes the characters of s from left to right.
The robot has two actions:
- Take the next character from
sand append it to its internal buffer. - Remove one character from the end of the internal buffer and print it.
At any time, you may choose either action as long as it is valid. Eventually, all characters must be taken from s and printed exactly once.
Return the lexicographically smallest string the robot can print.
The internal buffer behaves like a stack: the most recently added character is the next one that can be printed.
Goal
Construct the smallest possible output string under these rules.
Input Format
- A single string
s. - The string contains lowercase English letters.
Output Format
- Return the lexicographically smallest string that can be printed by the robot.
Constraints
1 <= s.length.scontains only lowercase English letters.- The exact upper bound is not required for practice; the intended solution should be linear or near-linear in the length of
s.
Example 1
Input
s = "zza"
Output
"azz"
Explanation
Take 'z', take 'z', take 'a', then print characters in the best order to get "azz".
Example 2
Input
s = "bac"
Output
"abc"
Explanation
One optimal sequence is to push 'b', then 'a', print 'a', print 'b', then process 'c' and print it, producing "abc".
Show 1 more example
Example 3
Input
s = "bdda"
Output
"addb"
Explanation
By delaying prints until smaller letters are available, the robot can produce "addb".
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.