Reorder the characters of a string by repeatedly moving the leftmost character to an auxiliary stack, then output the lexicographically smallest possible result.
Problem
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:
- push it onto the stack, or
- move characters from the stack to the output.
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.
Input Format
- A single line containing a string .
- The string contains lowercase English letters only.
Output Format
- Print one string: the lexicographically smallest string that can be obtained.
Constraints
- consists only of lowercase English letters.
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
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.