Balanced Reversals || codechef solution

Rajnish Tripathi 05:30

 

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

  • 1≤�≤100
  • 1≤�≤105
  • Sum of � over all test cases does not exceed 2⋅105.

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:-



Tags: