Bob and the minimum string

★★★★★

4.3

6 votes

Basics of Greedy Algorithms, Greedy Algorithms, Algorithms

Details

Problem

Bob has been provided a string $S$ of size $N$ containing lowercase characters. He took two empty strings, $U$ and $V$ , and performed the following operations:

Extract the first character from string $S$ and append it at the end of string $U$ .
Extract the last character from string $U$ and append it at the end of string $V$ .

Bob can perform the above operations any number of times. After some operations, he wants to get the string $S$ and $U$ empty, and string $V$ should be lexicographically minimum.

Your task is to help Bob find the lexicographically minimum possible string $V$ that can be formed.

Input Format:

The first line of input contains an integer $T$ , denoting the number of test cases.
For each test case, the first line will contain integer $N$ , the size of the input string $S$ , and the second line will contain the string $S$ itself.

Output format:

For each test case, print the lexicographically minimum possible string $V$ that can be formed.

Constraints:

$1 <= T <= 5$

$1 <= N <= 10^5$

$S[i]$ will be a lowercase english character.

Sample Input

2
4
acda
1
a

Sample Output

aadc
a

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For the first test case:

First, we will append char $a$ at the end of string $U$ and then pop it and append at the end of string $V$ .
Then we append char $c$ , $d$ , and $a$ at string $U$ and pop them one by one to get the final string $aadc$ .

For the second test case:

Here string of length one and there is no other combination possible hence the answer is the string $a$ .

Contributers:

Rohit Pradhan

Ujjwal Dwivedi