Removal of Unattractive Pairs (Codeforces 1907C)
Tags: Greedy, strings

Vlad found a string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters, and he wants to make it as short as possible.To do this, he can remove any pair of adjacent characters from $$$s$$$ any number of times, provided they are different. For example, if $$$s$$$=racoon, then by removing one pair of characters he can obtain the strings coon, roon, raon, and raco, but he cannot obtain racn (because the removed letters were the same) or rcon (because the removed letters were not adjacent).What is the minimum length Vlad can achieve by applying any number of deletions?

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Descriptions of the test cases follow.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$s$$$.The second line of each test case contains the string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single number—the minimum length of the string $$$s$$$, after removing pairs of adjacent characters with different values.

Note: In the first test case of the example, you need to act as follows: "aabc" $$$\rightarrow$$$ "ac" $$$\rightarrow$$$ "". Note that with a different order of deletions, the string will not become empty.

Sample Inputs:
10
4
aabc
5
abaca
10
avbvvcvvvd
7
abcdefg
5
dabbb
8
aacebeaa
7
bbbbacc
6
dacfcc
6
fdfcdc
9
dbdcfbbdc

Sample Outputs:
0
1
2
1
1
0
1
0
0
1

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

def main():
    orda = ord('a')
    for _ in range(int(input())):
        n = int(input())
        s = input()
        cnt = [0] * 26
        for i in range(n):
            cnt[ord(s[i]) - orda] += 1
        mx = max(cnt)
        print(max(2 * mx - n, n % 2))
if __name__ == '__main__':
    main()

Solution (Python):
def count_chars(string):
    chars_count = {}
    for char in string:
        if char in chars_count:
            chars_count[char] += 1
        else:
            chars_count[char] = 1
    return chars_count

def find_max_value(dictionary):
    max_value = 0
    for value in dictionary.values():
        if value > max_value:
            max_value = value
    return max_value

def solution(string):
    chars_count = count_chars(string)
    max_value = find_max_value(chars_count)
    if max_value > len(string) / 2:
        return len(string) - 2 * (len(string) - max_value)
    elif len(string) % 2 == 0:
        return 0
    else:
        return 1

def main():
    number_of_inputs = int(input())
    ans_list = []
    for i in range(number_of_inputs):
        string_length = int(input())
        string = input()
        ans_list.append(solution(string))
    for ans in ans_list:
        print(ans)
    return
main()

Solution (Python):
from sys import stdin
from collections import Counter
from heapq import heappush, heappop
T = int(stdin.readline())
for t in range(T):
    n = int(stdin.readline())
    counts = Counter(stdin.readline()[:n])
    mc = max(counts.values())
    print(max(mc - (sum(counts.values()) - mc), n % 2))