Count the Number of Pairs
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.
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.
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$$$.
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$$$.
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))
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')
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))