Instructions: The precise input-output format will be speci ed by Programming TAs for submission on Hackerearth.
Problem 1. You are playing a game that allows the following moves. Given an initial string of characters s and empty strings t and u initially. The moves are :
Remove a character from the front of s and append it to the end of t. Remove a character from the end of t and append it to the end of u.
The game ends when s is empty and t is empty and the answer of the game is u. Design a program that makes u to be lexicographically the smallest string possible. For example, suppose the input is cab. Then, consider the following moves.
s t u
cab
ab c
ca
c a cb a c ab abc
Clearly, abc is lexicographically the smallest string possible for u.
Example 2. Consider the input string s = acdb.
s
t
u
acdb
cdb
a
cdb
a
db
c
a
b
cd
a
cdb
a
cd
ab
c
abd
abdc
The smallest string in lexicographic order possible is abdc.
1
