7318: CodeChef SSUBSTR - Sorted Substrings
[Creator : ]
Description
You have a binary string S. You can perform the following operation on S:
Find the minimum number of operations required so that the final binary string S is sorted in non-decreasing order.
Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.
- Select any substring $S_{L \dots R}\ (1 \le L \le R \le |S|)$ which is sorted in non-decreasing order and remove it from S. Both the left and right halves are concatenated after performing the operation
Find the minimum number of operations required so that the final binary string S is sorted in non-decreasing order.
Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.
Input
The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
The first line of each test case contains an integer $N$ — the length of the binary string $S$.
The second line of each test case contains a binary string S of length N containing 0s and 1s only.
The first line of each test case contains an integer $N$ — the length of the binary string $S$.
The second line of each test case contains a binary string S of length N containing 0s and 1s only.
Output
For each test case, output the minimum number of operations required so that the final binary string SS is sorted in non-decreasing order.
Constraints
$1≤T≤10^5$
$1 \leq N \leq 10^5$
S contains 0 and 1 only.
The sum of N over all test cases won't exceed $2 \cdot 10^5$.
$1 \leq N \leq 10^5$
S contains 0 and 1 only.
The sum of N over all test cases won't exceed $2 \cdot 10^5$.
Sample 1 Input
3
3
000
5
01110
2
10
Sample 1 Output
0
1
1
Test case 1: The binary string is already sorted, so we need no operations.
Test case 2: We can use one operation to remove the sorted substring $S_{2 \dots 4} = 111$. Thus, the remaining string 00 is sorted.
Test case 3: We can use one operation to remove the sorted substring $S_{2 \dots 2} = 0$. Thus, the remaining string 1 is sorted.
Test case 2: We can use one operation to remove the sorted substring $S_{2 \dots 4} = 111$. Thus, the remaining string 00 is sorted.
Test case 3: We can use one operation to remove the sorted substring $S_{2 \dots 2} = 0$. Thus, the remaining string 1 is sorted.