Reverse Binary Strings (Codeforces 1437B)
Tags: Greedy, constructive algorithms

You are given a string $$$s$$$ of even length $$$n$$$. String $$$s$$$ is binary, in other words, consists only of 0's and 1's.String $$$s$$$ has exactly $$$\frac{n}{2}$$$ zeroes and $$$\frac{n}{2}$$$ ones ($$$n$$$ is even).In one operation you can reverse any substring of $$$s$$$. A substring of a string is a contiguous subsequence of that string.What is the minimum number of operations you need to make string $$$s$$$ alternating? A string is alternating if $$$s_i \neq s_{i + 1}$$$ for all $$$i$$$. There are two types of alternating strings in general: 01010101... or 10101010...

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$; $$$n$$$ is even) — the length of string $$$s$$$.The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$ ($$$s_i \in$$$ {0, 1}). String $$$s$$$ has exactly $$$\frac{n}{2}$$$ zeroes and $$$\frac{n}{2}$$$ ones.It's guaranteed that the total sum of $$$n$$$ over test cases doesn't exceed $$$10^5$$$.

Output: For each test case, print the minimum number of operations to make $$$s$$$ alternating.

Note: In the first test case, string 10 is already alternating.In the second test case, we can, for example, reverse the last two elements of $$$s$$$ and get: 0110 $$$\rightarrow$$$ 0101.In the third test case, we can, for example, make the following two operations:   11101000 $$$\rightarrow$$$ 10101100;  10101100 $$$\rightarrow$$$ 10101010. 

Sample Inputs:
3
2
10
4
0110
8
11101000

Sample Outputs:
0
1
2

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    s = input()
    on = s.count('10')
    nols = s.count('01')
    print(min(n // 2 - on, n // 2 - nols))

Solution (Python):
def solve():
    for _ in range(int(input())):
        length = int(input())
        s = input()
        count = 0
        for i in range(length - 1):
            if s[i] == s[i + 1]:
                count += 1
        print((count + 1) // 2)
solve()

Solution (Python):
test_cases = int(input())
for i in range(test_cases):
    str_len = int(input())
    str = input()
    bad_links = 0
    if str[0] == str[-1]:
        bad_links += 1
    for i in range(str_len - 1):
        if str[i] == str[i + 1]:
            bad_links += 1
    print(int(bad_links / 2))