A16177 | Chemistry
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are given a string $s$ of length $n$ , consisting of lowercase Latin letters, and an integer $k$ .
You need to check if it is possible to remove exactly $k$ characters from the string $s$ in such a way that the remaining characters can be rearranged to form a palindrome. Note that you can reorder the remaining characters in any way.
A palindrome is a string that reads the same forwards and backwards. For example, the strings "z", "aaa", "aba", "abccba" are palindromes, while the strings "codeforces", "reality", "ab" are not.
You need to check if it is possible to remove exactly $k$ characters from the string $s$ in such a way that the remaining characters can be rearranged to form a palindrome. Note that you can reorder the remaining characters in any way.
A palindrome is a string that reads the same forwards and backwards. For example, the strings "z", "aaa", "aba", "abccba" are palindromes, while the strings "codeforces", "reality", "ab" are not.
输入格式
Each test consists of multiple test cases. The first line contains a single integer $t$ ( $1 \leq t \leq 10^4$ ) — the number of the test cases. This is followed by their description.
The first line of each test case contains two integers $n$ and $k$ ( $0 \leq k < n \leq 10^5$ ) — the length of the string $s$ and the number of characters to be deleted.
The second line of each test case contains a string $s$ of length $n$ , consisting of lowercase Latin letters.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
The first line of each test case contains two integers $n$ and $k$ ( $0 \leq k < n \leq 10^5$ ) — the length of the string $s$ and the number of characters to be deleted.
The second line of each test case contains a string $s$ of length $n$ , consisting of lowercase 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, output "YES" if it is possible to remove exactly $k$ characters from the string $s$ in such a way that the remaining characters can be rearranged to form a palindrome, and "NO" otherwise.
You can output the answer in any case (uppercase or lowercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive answers.
You can output the answer in any case (uppercase or lowercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive answers.
输入输出样例
输入 #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
In the first test case, nothing can be removed, and the string "a" is a palindrome.
In the second test case, nothing can be removed, but the strings "ab" and "ba" are not palindromes.
In the third test case, any character can be removed, and the resulting string will be a palindrome.
In the fourth test case, one occurrence of the character "a" can be removed, resulting in the string "bb", which is a palindrome.
In the sixth test case, one occurrence of the characters "b" and "d" can be removed, resulting in the string "acac", which can be rearranged to the string "acca".
In the ninth test case, one occurrence of the characters "t" and "k" can be removed, resulting in the string "aagaa", which is a palindrome.
In the second test case, nothing can be removed, but the strings "ab" and "ba" are not palindromes.
In the third test case, any character can be removed, and the resulting string will be a palindrome.
In the fourth test case, one occurrence of the character "a" can be removed, resulting in the string "bb", which is a palindrome.
In the sixth test case, one occurrence of the characters "b" and "d" can be removed, resulting in the string "acac", which can be rearranged to the string "acca".
In the ninth test case, one occurrence of the characters "t" and "k" can be removed, resulting in the string "aagaa", which is a palindrome.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted