Swap and Delete
Contest: Educational Codeforces Round 160 (Rated for Div. 2)
Difficulty rating: 1000
Tags: strings

You are given a binary string $$$s$$$ (a string consisting only of 0-s and 1-s).

You can perform two types of operations on $$$s$$$:

1. delete one character from $$$s$$$. This operation costs $$$1$$$ coin;
2. swap any pair of characters in $$$s$$$. This operation is free (costs $$$0$$$ coins).

You can perform these operations any number of times and in any order.

Let's name a string you've got after performing operations above as $$$t$$$. The string $$$t$$$ is good if for each $$$i$$$ from $$$1$$$ to $$$|t|$$$ $$$t_i \neq s_i$$$ ($$$|t|$$$ is the length of the string $$$t$$$). The empty string is always good. Note that you are comparing the resulting string $$$t$$$ with the initial string $$$s$$$.

What is the minimum total cost to make the string $$$t$$$ good?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of each test case contains a binary string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$; $$$s_i \in \{$$$0, 1$$$\}$$$) — the initial string, consisting of characters 0 and/or 1.

Additional constraint on the input: the total length of all strings $$$s$$$ doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print one integer — the minimum total cost to make string $$$t$$$ good.

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

Note:
In the first test case, you have to delete a character from $$$s$$$ to get the empty string $$$t$$$. Only then $$$t$$$ becomes good. One deletion costs $$$1$$$ coin.

In the second test case, you can, for example, delete the second character from $$$s$$$ to get the string 01, and then swap the first and second characters to get the string $$$t$$$ $$$=$$$ 10. String $$$t$$$ is good, since $$$t_1 \neq s_1$$$ and $$$t_2 \neq s_2$$$. The total cost is $$$1$$$ coin.

In the third test case, you can, for example, swap $$$s_1$$$ with $$$s_2$$$, swap $$$s_3$$$ with $$$s_4$$$, swap $$$s_5$$$ with $$$s_7$$$, $$$s_6$$$ with $$$s_8$$$ and $$$s_9$$$ with $$$s_{10}$$$. You'll get $$$t$$$ $$$=$$$ 1010001110. All swap operations are free, so the total cost is $$$0$$$.

Example input:
4
0
011
0101110001
111100

Example output:
1
1
0
4

Editorial:
Let's count the number of 0-s and 1-s in $$$s$$$ as $$$cnt_0$$$ and $$$cnt_1$$$ correspondingly. Since $$$t$$$ consists of characters from $$$s$$$ then $$$t$$$ will contain no more than $$$cnt_0$$$ zeros and $$$cnt_1$$$ ones.
Let's build $$$t$$$ greedily, since we always compare $$$t$$$ with prefix of $$$s$$$. Suppose the length of $$$t$$$ is at least one, it means that $$$t_1$$$ must be different from $$$s_1$$$, so if $$$s_1$$$ $$$=$$$ 0 we must set $$$t_1$$$ $$$=$$$ 1. So let's check that we have at least one 1 (or $$$cnt_1 > 0$$$), take 1 and place it at $$$t_1$$$. Case $$$s_1$$$ $$$=$$$ 1 is the same.
After placing $$$t_1$$$ we can analogically try to place $$$t_2$$$ and so on until we run out of necessary digits or build the whole string of length $$$|s|$$$.
We've built the longest possible string $$$t$$$ in $$$O(|s|)$$$ time, so the answer is $$$|s| - |t|$$$.