Codeforces Round 905 (Div. 3) |
---|
Закончено |
Вам дана строка $$$s$$$ длины $$$n$$$, состоящая из строчных латинских букв, и число $$$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$$$ и количество символов, которые нужно удалить.
Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите «YES», если можно удалить из строки $$$s$$$ ровно $$$k$$$ символов, чтобы из оставшихся символов можно было собрать палиндром, и «NO» иначе.
Вы можете вывести ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительные ответы.
141 0a2 0ab2 1ba3 1abb3 2abc6 2bacacd6 2fagbza6 2zwaafa7 2taagaak14 3ttrraakkttoorr5 3debdb5 4ecadc5 3debca5 3abaac
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», которая является палиндромом.
Название |
---|