Count the Number of Pairs

题意翻译

给定 $n$，$k$，长度为 $n$ 的字符串 $s$。 一个大写的字母和一个小写格式的该字母可以合并，合并后消失，且分值加一。 一次操作定义为将一个字母改变其大小写格式（大写转小写，小写转大写）。 求在不超过 $k$ 次操作后，该字符串的分值的最大值。 共 $t$ 组数据。 by @Larryyu

题目描述

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

输入输出样例

输入样例 #1

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

输出样例 #1

5
0
1
3
2

说明

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.

题目大意：
给定一个字符串 $ s $ 的长度 $ n $ 和最大操作次数 $ k $，字符串 $ s $ 由小写和大写拉丁字母组成。每对匹配的大写和小写字母可以合并并获得一分，但字母对不能重叠。可以通过不超过 $ k $ 次操作来改变字母的大小写格式，求字符串的最大得分。有多组数据。

输入输出数据格式：
输入格式：
- 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数 $ n $（$ 1 \le n \le 2 \cdot 10^5 $）和 $ k $（$ 0 \le k \le n $），分别表示字符串的长度和最大操作次数。
- 每个测试用例的第二行包含一个长度为 $ n $ 的字符串 $ s $，由小写和大写拉丁字母组成。

输出格式：
- 对于每个测试用例，输出一行，包含一个整数，表示字符串 $ s $ 的最大得分。题目大意： 给定一个字符串 $ s $ 的长度 $ n $ 和最大操作次数 $ k $，字符串 $ s $ 由小写和大写拉丁字母组成。每对匹配的大写和小写字母可以合并并获得一分，但字母对不能重叠。可以通过不超过 $ k $ 次操作来改变字母的大小写格式，求字符串的最大得分。有多组数据。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数 $ n $（$ 1 \le n \le 2 \cdot 10^5 $）和 $ k $（$ 0 \le k \le n $），分别表示字符串的长度和最大操作次数。 - 每个测试用例的第二行包含一个长度为 $ n $ 的字符串 $ s $，由小写和大写拉丁字母组成。 输出格式： - 对于每个测试用例，输出一行，包含一个整数，表示字符串 $ s $ 的最大得分。