# Balanced Reversals || codechef solution

## Problem

Chef is given a binary string $�$ of length $�$. He can perform the following operation on $�$ any number of times:

• Choose $�$ and $�$ $\left(1\le �\le �\le �\right)$, such that, in the substring $�\left[�,�\right]$, the number of $1$s is equal to the number of $0$s and reverse the substring $�\left[�,�\right]$.

Find the lexicographically smallest string that Chef can obtain after performing the above operation any (possibly zero) number of times on $�$.

String $�$ is lexicographically smaller than string $�$, if either of the following satisfies:

• $�$ is a prefix of $�$ and $�\mathrm{\ne }�$.
• There exists an index $�$ such that ${�}_{�}<{�}_{�}$ and ${�}_{�}={�}_{�},\mathrm{\forall }�$ such that $1\le �<�$.

### Input Format

• First line will contain $�$, the number of test cases. Then the test cases follow. Each test case contains two lines.
• The first line contains the integer $�$, the length of the binary string.
• The second line contains the binary string $�$.

### Output Format

For each test case, print the lexicographically smallest binary string that can be obtained after performing the operation any (possibly zero) number of times.

### Constraints

• $1\le �\le 100$
• $1\le �\le 1{0}^{5}$
• Sum of $�$ over all test cases does not exceed $2\cdot 1{0}^{5}$.

### Sample 1:

Input
Output
2
5
01100
4
0000

00011
0000

### Explanation:

Test Case $1$: Chef can choose $�=2$ and $�=5$. The chosen substring, $�\left[2,5\right]=1100$. On reversing this, we get $0011$. Thus, the final string is $�=00011$. Note that this is the lexicographically smallest string possible.

Test Case $2$: Since the string is already lexicographically minimum, Chef does not need to apply any operation.

Code(c++):-

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
sort(s.begin(),s.end());
cout<<s<<endl;
}
return 0;
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-