Header Ads Widget

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  (1), such that, in the substring [,], the number of 1s is equal to the number of 0s and reverse the substring [,].

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 .
  • There exists an index  such that < and =, such that 1<.

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

  • 1100
  • 1105
  • Sum of  over all test cases does not exceed 2105.

Sample 1:

Input
Output
2
5
01100
4
0000
00011
0000

Explanation:

Test Case 1: Chef can choose =2 and =5. The chosen substring, [2,5]=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() {
    // your code goes here
    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:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-