Problem Statement

Lexicographically Smallest String from Operations Problem Description Nadia was handed a string s , at most 105 characters long, and decided to play a small puzzle game with it. She sets up two more strings, t and u , both empty to start, and allows herself two kinds of moves: Remove the first character of s and append it onto t . (Equivalently, push that character onto a stack t .) Remove the last character of s and append it onto u . At any point in the game she may also pop the top character off of t (as long as t isn't empty) and append it to u . Nadia wants to finish with both s and t completely emptied out, while u ends up as lexicographically small as possible. Write a program that plays the game on Nadia's behalf and returns the smallest possible string u she can end up with. A string a is lexicographically smaller than string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding l