Minimal String Game

Petya recieved a gift of a string s with length up to 105 characters for his birthday. He took two more empty strings t and u and decided to play a game. This game has two possible moves:

  • Extract the first character of s and append t with this character.
  • Extract the last character of t and append u with this character.

Petya wants to get strings s and t empty and string u lexicographically minimal.

Example :

First I think find Minimum of string s lets assume it be ‘a’ and then push every elemnt fromstring to stack untill we encounter ‘a’. then pop each element from stack and push into queue. and repeat same for string s from character ‘a’ to another minimum character of string…
But it is totally wrong!!
Any Hint or Help