Smallest String Through a Holding Stack

You're given a string s of lowercase letters, and you start with an empty holding stack and an empty output string.

You may repeat either move, in any order:

1. Load: take the first character of s off the front and push it onto the stack.
2. Emit: pop the top character of the stack and append it to the output.

Keep going until both s and the stack are empty. Return the lexicographically smallest output you can produce.

Example 1

Input:  s = "cab"
Output: "abc"

Load c and a, then emit a. Load b, then emit b and c.

Example 2

Input:  s = "bdab"
Output: "abdb"

To emit a first you have to load b, d and a. After emitting a, d is on top of the stack and blocks the b underneath, so "abbd" can't be produced.

Example 3

Input:  s = "dbca"
Output: "acbd"

Nothing can be emitted before a, so every character has to be loaded first. After that the stack only gives back c, b, d.

Constraints

• 1 <= s.length <= 10^5
• s contains only lowercase English letters.