Swap and Delete (Codeforces 1913B)
Tags: Others, 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$$$:   delete one character from $$$s$$$. This operation costs $$$1$$$ coin;  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: 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: For each test case, print one integer — the minimum total cost to make string $$$t$$$ good.

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$$$.

Sample Inputs:
4
0
011
0101110001
111100

Sample Outputs:
1
1
0
4

Solution (Python):
from sys import stdin
input = stdin.readline

def ri():
    return int(input())

def rl(v_type=int, output=list):
    return output(map(v_type, input().split()))

def rs():
    return input()[:-1]

def out(x, sep='\n'):
    print(sep.join(x))

def solve():
    s = rs()
    n = len(s)
    count0 = s.count('0')
    count1 = s.count('1')
    if count0 == count1:
        return 0
    for i in range(n):
        if s[i] == '0':
            count1 -= 1
            if count1 == -1:
                return n - i
        else:
            count0 -= 1
            if count0 == -1:
                return n - i
outp = []
for TC in range(ri()):
    outp.append(str(solve()))
out(outp)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
MOD = 1000000007
input = sys.stdin.readline

def debug(*args):
    print(*args, file=sys.stderr)

def solve():
    s = input().strip()
    n = len(s)
    count_0 = s.count('0')
    count_1 = s.count('1')
    if count_0 == count_1:
        print(0)
        return
    for i in range(n):
        if s[i] == '0':
            count_1 -= 1
            if count_1 == -1:
                print(n - i)
                break
        else:
            count_0 -= 1
            if count_0 == -1:
                print(n - i)
                break
t = int(sys.stdin.readline().strip())
for _ in range(t):
    solve()

Solution (Python):
def main():
    from sys import stdin
    e = stdin.readline
    d = {'0': 1, '1': 0}
    for _ in range(int(e())):
        s = e().strip()
        p = [s.count(c) for c in '01']
        u = len(s)
        for c in s:
            if not p[d[c]]:
                break
            p[d[c]] -= 1
            u -= 1
        print(u)
main()