[Solution] Balanced Reversals solution codechef

Balanced Reversals solution codechef – Chef is given a binary string AA of length NN. He can perform the following operation on AA any number of times:

  • Choose LL and RR (1LRN)(1≤L≤R≤N), such that, in the substring A[L,R]A[L,R], the number of 11s is equal to the number of 00s and reverse the substring A[L,R]A[L,R].

Balanced Reversals solution codechef

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

String XX is lexicographically smaller than string YY, if either of the following satisfies:

  • XX is a prefix of YY and XYX≠Y.
  • There exists an index ii such that Xi<YiXi<Yi and Xj=Yj,jXj=Yj,∀j such that 1j<i1≤j<i.

Input Format

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

Balanced Reversals solution codechef

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

  • 1T1001≤T≤100
  • 1N1051≤N≤105
  • Sum of NN over all test cases does not exceed 21052⋅105.

Sample Input 1 

2
5
01100
4
0000

Balanced Reversals solution codechef

 

00011
0000

Balanced Reversals Explanation

Test Case 11: Chef can choose L=2L=2 and R=5R=5. The chosen substring, A[2,5]=1100A[2,5]=1100. On reversing this, we get 00110011. Thus, the final string is A=00011A=00011. Note that this is the lexicographically smallest string possible.

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

Leave a Comment