Ugu
Contest: Codeforces Round 830 (Div. 2)
Difficulty rating: 900
Tags: brute force, dp, greedy, implementation

A binary string is a string consisting only of the characters 0 and 1. You are given a binary string $$$s_1 s_2 \ldots s_n$$$. It is necessary to make this string non-decreasing in the least number of operations. In other words, each character should be not less than the previous. In one operation, you can do the following:

- Select an arbitrary index $$$1 \leq i \leq n$$$ in the string;
- For all $$$j \geq i$$$, change the value in the $$$j$$$-th position to the opposite, that is, if $$$s_j = 1$$$, then make $$$s_j = 0$$$, and vice versa.

What is the minimum number of operations needed to make the string non-decreasing?

Input format:
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of test cases follows.

The first line of each test cases a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the string.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the minimum number of operations that are needed to make the string non-decreasing.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the string is already non-decreasing.

In the second test case, you can select $$$i = 1$$$ and then $$$s = \mathtt{01}$$$.

In the third test case, you can select $$$i = 1$$$ and get $$$s = \mathtt{010}$$$, and then select $$$i = 2$$$. As a result, we get $$$s = \mathtt{001}$$$, that is, a non-decreasing string.

In the sixth test case, you can select $$$i = 5$$$ at the first iteration and get $$$s = \mathtt{100001}$$$. Then choose $$$i = 2$$$, then $$$s = \mathtt{111110}$$$. Then we select $$$i = 1$$$, getting the non-decreasing string $$$s = \mathtt{000001}$$$.

Example input:
8
1
1
2
10
3
101
4
1100
5
11001
6
100010
10
0000110000
7
0101010

Example output:
0
1
2
1
2
3
1
5

Editorial:
Let's mentally imagine the following array of length $$$n - 1$$$: $$$a_i = 0$$$ if $$$s_i = s_{i+1}$$$, and $$$1$$$ otherwise. Note that if we apply the operation to the index $$$i$$$, then all the values ​​of the array $$$a$$$ do not change, except for $$$a_{i - 1}$$$. Let's look at this in more detail:
• For $$$i \leq j$$$, note that the $$$j$$$th and $$$(j+1)$$$th elements invert their value, so $$$a_j$$$ does not change.
• For $$$j < i - 1$$$, note that the $$$j$$$-th and $$$(j+1)$$$-th elements do not change their value, so $$$a_j$$$ does not change.
• For $$$j = i - 1$$$, note that the $$$j$$$th element does not change its value, but the $$$(j+1)$$$th element does, so $$$a_j$$$ will change its value.
If we look at the array $$$a$$$ for a sorted binary string, we can see that this array does not contain more than one unit (you either have a string consisting of only zeros or only ones, or it looks like this — $$$0000\ldots01\ldots11111$$$ ).
Let $$$s$$$ be the number of ones in the original array $$$a$$$. We have now shown that the answer is $$$\geq \max(s - 1, 0)$$$. In fact, if the string starts with $$$0$$$, then the answer is $$$\max(s - 1, 0)$$$, otherwise it is $$$s$$$.
Let's prove that if the string starts with $$$0$$$, then we can get the answer $$$\max(s - 1, 0)$$$ (the case with $$$1$$$ will be similar). Let's show a constructive proof using a small example $$$s = 0001110010$$$:
• Choose $$$i = 3$$$, then $$$s = 0000001101$$$,
• Choose $$$i = 7$$$, then $$$s = 0000000010$$$,
• Choose $$$i = 9$$$, then $$$s = 0000000001$$$.