Reorder the characters of a string by repeatedly moving the leftmost character to an auxiliary stack, then output the lexicographically smallest possible result.
You are given a string consisting of lowercase Latin letters.
You may process the string from left to right using one auxiliary stack. At any moment, you can take the next character from the front of the unprocessed part and either:
Your goal is to produce the lexicographically smallest possible output string.
In practice, this means you must decide when a character is safe to remove from the stack and append to the answer so that no smaller character remains to its right in the unprocessed suffix.
Return the smallest string that can be formed under these rules.
Example 1
Input
acdb
Output
abdc
Explanation
After processing the string, the smallest valid output is obtained by delaying larger characters until it is safe to place them after smaller ones.
Example 2
Input
bca
Output
acb
Explanation
The character 'a' must appear before 'b' and 'c' in the smallest valid arrangement.
Premium problem context
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.