Using a Robot to Print the Lexicographically Smallest String
Medium · Stack & Monotonic Stack · about 25 minutes
Asked at Google, Amazon, Microsoft.
A robot works with two strings: s (the input) and t, which starts out empty. At each step it can either take the first character of s and append it to t, or take the last character of t and write it on paper (appending to what's already written). Once both s and t are used up, what is the alphabetically smallest text that can be on the paper?