This problem was proposed at Ozon internal contest system for juniors and trainees. I joined the company
recently and was just in time to participate in test contest. Organizers kindly allowed to share a couple
problems (another was Pages to Print) - thanks a lot, though original author
is unknown.
Given a string of small latin letters, we want to modify it so that it becomes lexicographically smaller - as small as possible. The modification allowed is very simple - pluck out some letter (only one) and reinsert it somewhere.
Input data provide the number T of testcases in the first line.
Next lines contain one string each.
Answer should contain modified strings, space-separated.
Example
input:
5
bca
abdecf
adbce
bcd
a
answer:
abc abcdef abcde bcd a
P.S. Original problem allowed strings up to half-million character length, which prohibits using inefficient
logic (something O(N^3) is obvious). However in this task we can't easily handle such amounts of data and,
what is worse, can't keep them secret from user (as was the case in the contest). Perhaps we may add advanced
version of the problem later, if it may be interesting.