Using a Robot to Print the Lexicographically Smallest String
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 the string
sand give it to the robot. The robot will append this character to the stringt. - Remove the last character of the string
tand 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"By moving all characters from
s to t and then writing from t, the robot can produce azz, which is lexicographically smallest.Example 2
Input
s = "bac"Output
"abc"The robot can write
a and b from t, then move and write c, producing the lexicographically smallest string abc.Constraints
- 1 <= s.length <= 10^5
- s consists of only English lowercase letters.