# Sort the String CodeChef Solution

Hey Coders, Here Your Solution Sort the String CodeChef Solution

## Sort the String Problem Code: SRTARR

You have a binary string SS of length NN. In one operation you can select a substring of SS and reverse it. For example, on reversing the substring S[2,4]S[2,4] for S=11000S=11000, we change 110001001011000→10010.

Find the minimum number of operations required to sort this binary string.
It can be proven that the string can always be sorted using the above operation finite number of times.

### Input Format

• The first line of input will contain a single integer TT, denoting the number of test cases.
• Each test case consists of 22 lines of input.
• The first line of each test case contains a single integer NN — the length of the binary string.
• The second line of each test case contains a binary string SS of length NN.

### Output Format

For each test case, output on a new line — the minimum number of operations required to sort the binary string.

## Sort the String CodeChef Solution

### Constraints

• 1T21051≤T≤2⋅105
• 1N21051≤N≤2⋅105
• Sum of NN over all test cases does not exceed 106106.
• String SS consists of only ‘00‘s and ‘11‘s.

### Sample Input 1

4
3
000
4
1001
4
1010
6
010101


### Sample Output 1

0
1
2
2


## Sort the String CodeChef Solution

Test case 11: The string is already sorted, hence, zero operations are required to sort it.

Test case 22: We can sort the string in the following way: 10011001  00110011.

Test case 33: We can sort the string in the following way:
10101010  11001100  00110011.
It can be proven that this string cannot be sorted in less than 22 operations.

Test case 44: We can sort the string in the following way:
010101010101  001011001011  000111000111.
It can be proven that this string cannot be sorted in less than 22 operations.

## SOLUTION

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.

If You Want To Learn Something New Then Visit Our Official Channel YOUTUBE

## 2 thoughts on “Sort the String CodeChef Solution”

1. I like what you guys are up also. Such clever work and reporting! Keep up the superb works guys I’ve incorporated you guys to my blogroll. I think it will improve the value of my web site 🙂