Sort String | Practice Problems

Sort String

★★★★★

1.6

17 votes

, Algorithms, Greedy algorithm, Linear Search

Details

Submissions

Discussion

Editorial

Problem

You are given a binary string $S$ of length $N$ . You can apply the following operation to the string $S$ :

Choose two distinct indices $i, j\;(1 \le i, j\le N, i\neq j)$ and flip the characters $S_i, S_j$ .

Find the minimum number of operations required to sort the given string $S$ . It is always possible to sort any string under the given constraints.

Input format

The first line contains $T$ denoting the number of test cases. The description of $T$ test cases is as follows:
For each test case:
- The first line contains $N$ denoting the length of string $S$ .
- The second line contains the binary string $S$ .

Output format

For each test case, print the minimum number of operations required to sort the given string $S$ .

Constraints

$1 \leq T \leq 10^5 \\ 1 \leq N \leq 3\cdot10^5\\ \\S \; contains\; '0's\; and\; '1's. \\ Sum\; of \; N\;over\;all\;test\;cases\;does\;not\;exceed\;3\cdot 10^5.$

Sample Input

Sample Output

1
2

Time Limit: 10

Memory Limit: 256

Source Limit:

Explanation

In the first test case, choose $i = 1, j=3$ and flip $S_1, S_3$ making $S=111$ which is a sorted string.

In the second test case, choose $i = 1, j=2$ and flip $S_1, S_3$ making $S=000100$ , then choose $i = 5, j=6$ and flip $S_5, S_6$ making $S=000111$ , which is a sorted string.

Contributers:

Soumyadeep Pal

Divyam Agarwal