← 返回题目列表

Codeforces · 1883/B

B. 化学

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,由小写拉丁字母和一个整数 $$$k$$$ 组成。

您需要检查是否可以从字符串 $$$s$$$ 中精确删除 $$$k$$$ 个字符,以便可以重新排列剩余字符以形成回文。请注意,您可以以任何方式对剩余字符重新排序。

回文是向前和向后读取相同内容的字符串。例如,字符串“z”、“aaa”、“aba”、“abccba”是回文,而字符串“codeforces”、“reality”、“ab”则不是。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。接下来是他们的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$0 \leq k < n \leq 10^5$$$) — 字符串 $$$s$$$ 的长度和要删除的字符数。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由小写拉丁字母组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果可以从字符串 $$$s$$$ 中精确删除 $$$k$$$ 个字符,使得剩余字符可以重新排列形成回文,则输出“YES”,否则输出“NO”。

您可以以任何大小写(大写或小写)输出答案。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案。

示例

输入 #1

14
1 0
a
2 0
ab
2 1
ba
3 1
abb
3 2
abc
6 2
bacacd
6 2
fagbza
6 2
zwaafa
7 2
taagaak
14 3
ttrraakkttoorr
5 3
debdb
5 4
ecadc
5 3
debca
5 3
abaac

输出 #1

YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
NO
YES

注意

在第一个测试用例中,无法删除任何内容,并且字符串“a”是回文。

在第二个测试用例中,无法删除任何内容,但字符串“ab”和“ba”不是回文。

在第三个测试用例中,可以删除任何字符,所得字符串将是回文。

在第四个测试用例中,可以删除一次出现的字符“a”,得到字符串“bb”,它是一个回文。

在第六个测试用例中,可以删除一次出现的字符“b”和“d”,从而得到字符串“acac”,可以将其重新排列为字符串“acca”。

在第九个测试用例中,可以删除字符“t”和“k”的一次出现,得到字符串“aagaa”,它是一个回文。