Count the Number of Pairs (Codeforces 1800B)
Tags: Greedy, strings

Kristina has a string $$$s$$$ of length $$$n$$$, consisting only of lowercase and uppercase Latin letters. For each pair of lowercase letter and its matching uppercase letter, Kristina can get $$$1$$$ burl. However, pairs of characters cannot overlap, so each character can only be in one pair.For example, if she has the string $$$s$$$ = "aAaaBACacbE", she can get a burl for the following character pairs:   $$$s_1$$$ = "a" and $$$s_2$$$ = "A"  $$$s_4$$$ = "a" and $$$s_6$$$ = "A"  $$$s_5$$$ = "B" and $$$s_{10}$$$ = "b"  $$$s_7$$$= "C" and $$$s_9$$$ = "c" Kristina wants to get more burles for her string, so she is going to perform no more than $$$k$$$ operations on it. In one operation, she can:  either select the lowercase character $$$s_i$$$ ($$$1 \le i \le n$$$) and make it uppercase.  or select uppercase character $$$s_i$$$ ($$$1 \le i \le n$$$) and make it lowercase. For example, when $$$k$$$ = 2 and $$$s$$$ = "aAaaBACacbE" it can perform one operation: choose $$$s_3$$$ = "a" and make it uppercase. Then she will get another pair of $$$s_3$$$ = "A" and $$$s_8$$$ = "a"Find maximum number of burles Kristina can get for her string.

Input: The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) and $$$k$$$ ($$$0 \le k \le n$$$) — the number of characters in the string and the maximum number of operations that can be performed on it.The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting only of lowercase and uppercase 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, print exactly one integer on a separate line: the maximum number of burles that Kristina can get for her string $$$s$$$.

Note: The first test case is explained in the problem statement.In the second test case, it is not possible to get any pair by performing any number of operations.

Sample Inputs:
5
11 2
aAaaBACacbE
2 2
ab
4 1
aaBB
6 0
abBAcC
5 3
cbccb

Sample Outputs:
5
0
1
3
2

Solution (Python):
import math

def pug_func(s: str, k: str) -> int:
    alphabet = 'abcdefghijklmnopqrstuvwxyz'
    d = {}
    for char in s:
        if char in d:
            d[char] += 1
        else:
            d[char] = 1
    i = 1
    ans = 0
    for char in alphabet:
        if char in d and char.upper() in d:
            if d[char] == d[char.upper()]:
                ans += d[char]
                d.pop(char)
                d.pop(char.upper())
            else:
                ans += min(d[char], d[char.upper()])
                if d[char] > d[char.upper()]:
                    d[char] = abs(d[char] - d[char.upper()])
                    d.pop(char.upper())
                else:
                    d[char.upper()] = abs(d[char] - d[char.upper()])
                    d.pop(char)
    for key in d:
        repl = d[key] // 2
        if repl < k:
            ans += repl
            k -= repl
        else:
            ans += k
            k = 0
            break
    return ans
t = int(input())
lista_ans = []
lista_k = []
for _ in range(t):
    (n, k) = input().split(' ')
    lista_k.append(int(k))
    s = input()
    lista_ans.append(s)
for (s, k) in zip(lista_ans, lista_k):
    print(pug_func(s, k))

Solution (Python):
import sys
input = sys.stdin.readline
print = sys.stdout.write
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    string = list(str(input()))
    string.pop()
    dictionary = {}
    money = 0
    for letter in string:
        if letter.lower() == letter:
            upper_letter = letter.upper()
            if upper_letter in dictionary:
                dictionary[upper_letter] -= 1
                money += 1
                if dictionary[upper_letter] == 0:
                    del dictionary[upper_letter]
            else:
                dictionary[letter] = dictionary.get(letter, 0) + 1
        elif letter.upper() == letter:
            lower_letter = letter.lower()
            if lower_letter in dictionary:
                dictionary[lower_letter] -= 1
                money += 1
                if dictionary[lower_letter] == 0:
                    del dictionary[lower_letter]
            else:
                dictionary[letter] = dictionary.get(letter, 0) + 1
    for (key, value) in dictionary.items():
        difference = value // 2
        if difference <= k:
            k -= difference
            money += difference
        else:
            money += k
            break
    print(f'{money} \n')

Solution (Python):
import math

def pug_func(s: str, k: str) -> int:
    alphabet = 'abcdefghijklmnopqrstuvwxyz'
    d = {}
    for char in s:
        if char in d:
            d[char] += 1
        else:
            d[char] = 1
    i = 1
    ans = 0
    for char in alphabet:
        if char in d and char.upper() in d:
            if d[char] == d[char.upper()]:
                ans += d[char]
                d.pop(char)
                d.pop(char.upper())
            else:
                ans += min(d[char], d[char.upper()])
                if d[char] > d[char.upper()]:
                    d[char] = abs(d[char] - d[char.upper()])
                    d.pop(char.upper())
                else:
                    d[char.upper()] = abs(d[char] - d[char.upper()])
                    d.pop(char)
    for key in d:
        repl = d[key] // 2
        if repl < k:
            ans += repl
            k -= repl
        else:
            ans += k
            k = 0
            break
    return ans
t = int(input())
lista_ans = []
lista_k = []
for _ in range(t):
    (n, k) = input().split(' ')
    lista_k.append(int(k))
    s = input()
    lista_ans.append(s)
for (s, k) in zip(lista_ans, lista_k):
    print(pug_func(s, k))