# PROBLEM LINK:

**Setter:** iceknight1093

**Testers:** tabr

**Editorialist:** aryanag_adm

# DIFFICULTY:

1282

# PREREQUISITES:

Sorting

# PROBLEM:

You are given a binary string S.

You are allowed to perform the following operation:

- Select any subsequence of length 2k
- Move the elements at the first k indices of the sequence to the beginning of the string, and those at the last k indices to the end of the string.

You may perform this operation any number of items. Output the lexicographically minimal string that you can reach.

# EXPLANATION:

Note that if |S| = 2, then the operations are ineffective, i.e, they do not change S. Therefore, in this case the answer is S itself.

Else, I claim that we can perform operations to sort S completely.

Proof:

If the string consists of only 1's or only 0's then we are done. Else, consider the element S_2. If S_2 = 1, then we perform the operation with the chosen subsequence being \{1, 2\}. This keeps S_1 fixed, and sends S_2 = 1 to the end of the string. Else, we perform the operation with the chosen subsequence being \{2, N\}. This keeps S_N fixed and sends S_2 = 0 to the beginning of the string.

Without loss in generality, assume that S_1 = 0 now (if S_N = 1 instead, you can perform symmetric operations). For every index i such that S_i = 1, you can now perform the operation \{1, i\}, which will keep S_1 the same but send S_i = 1 to the end of the string. Doing this repeatedly will sort the string.

Therefore, if N = 2 then we just output S. Else, we sort S and output that.

# TIME COMPLEXITY:

Both O(N) and O(N \log N) are easy.

My solution takes O(N \log N).

# SOLUTION:

## Editorialist's Solution

```
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <sys/resource.h>
#define double long double
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define mp(a, b) make_pair(a, b)
#define lz lazup(l, u, i);
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
if(n > 2) sort(s.begin(), s.end());
cout<<s<<endl;
}
}
```