Smallest number

★★★★★

3.4

7 votes

Algorithms, Basics of Greedy Algorithms, C++, Greedy Algorithms

Details

Submissions

Discussion

Editorial

Problem

You are given a string $S$ that represents a number. This string consists of the following characters only:

You can perform the following operation:

Swap any two adjacent characters only if the absolute difference between the characters is $1$

Your task is to determine the smallest number that can be formed by using the provided operation. You can perform this operation any number of times (possibly zero).

Note: Assume $1$ based indexing.

Input format

The first line contains an integer $T$ that denotes the number of test cases.
For each test case:
- The first line contains an integer that denotes the length of string $S$ .
- The second line contains a string that denotes the string $S$ .

Output format

For each test case, print a string representing the smallest number that can be formed in a new line.

Constraints

$1 \le T \le 10 \\ 1 \le |S| \le 10^5$

Time Limit: 0.5

Memory Limit: 256

Source Limit:

Explanation

For the first test case:

No operation is required. The number represented by the string $S$ is already smallest.

For the second test case:

Apply operation on character at $1^{st}$ and $2^{nd}$ position. String $S$ will be $123123$ .
Apply operation on character at $4^{th}$ and $5^{th}$ position. String $S$ will be $123213$ .
Apply operation on character at $3^{rd}$ and $4^{th}$ position. String $S$ will be $122313$ .
$122313$ is the smallest number that can be achieved.