CF1800B Count the Number of Pairs

Kristina 有一个长度为 $n$ 的字符串 $s$，该字符串只包含小写和大写拉丁字母。对于每一对小写字母及其对应的大写字母，Kristina 可以获得 $1$ 个 burl。然而，字符对不能重叠，所以每个字符只能属于一个对。 例如，如果她有字符串 $s = \text{"aAaaBACacbE"}$，她可以通过以下字符对获得 burl： - $s_1 = \text{"a"}$ 和 $s_2 = \text{"A"}$ - $s_4 = \text{"a"}$ 和 $s_6 = \text{"A"}$ - $s_5 = \text{"B"}$ 和 $s_{10} = \text{"b"}$ - $s_7 = \text{"C"}$ 和 $s_9 = \text{"c"}$ Kristina 想让她的字符串获得更多的 burl，因此她打算对字符串进行不超过 $k$ 次操作。每次操作，她可以： - 选择一个小写字符 $s_i$（$1 \le i \le n$），并将其变为大写。 - 或者选择一个大写字符 $s_i$（$1 \le i \le n$），并将其变为小写。 例如，当 $k = 2$ 且 $s = \text{"aAaaBACacbE"}$ 时，她可以进行一次操作：选择 $s_3 = \text{"a"}$ 并将其变为大写。然后她可以再获得一对 $s_3 = \text{"A"}$ 和 $s_8 = \text{"a"}$。 请你求出 Kristina 能为她的字符串 $s$ 获得的最大 burl 数。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$（$1 \le n \le 2 \times 10^5$）和 $k$（$0 \le k \le n$），分别表示字符串的长度和最多可以进行的操作次数。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，该字符串只包含小写和大写拉丁字母。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一行，包含一个整数，表示 Kristina 能为她的字符串 $s$ 获得的最大 burl 数。

第一个测试用例的解释见题目描述。 在第二个测试用例中，无论进行多少次操作，都无法获得任何一对。 由 ChatGPT 4.1 翻译