Назовем левым циклическим сдвигом некоторой строки $$$t_1 t_2 t_3 \dots t_{n - 1} t_n$$$ следующую строку: $$$t_2 t_3 \dots t_{n - 1} t_n t_1$$$.
Аналогично, назовем правым циклическим сдвигом строки $$$t$$$ строку $$$t_n t_1 t_2 t_3 \dots t_{n - 1}$$$.
Скажем, что строка $$$t$$$ является хорошей, если ее левый циклический сдвиг равен правому циклическому сдвигу.
Вам дана строка $$$s$$$, состоящая из цифр 0–9.
Какое минимальное количество символов необходимо удалить из строки $$$s$$$, чтобы она стала хорошей?
Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
Следующие $$$t$$$ строк содержат описание наборов входных данных. Первая и единственная строка каждого набора содержит строку $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$). Каждый символ $$$s_i$$$ является цифрой 0–9.
Гарантируется, что суммарная длина строк не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите минимальное количество символов, которое необходимо удалить из строки $$$s$$$, чтобы она стала хорошей.
3 95831 100120013 252525252525
3 5 0
В первом примере можно стереть любые $$$3$$$ символа, например $$$1$$$-й, $$$3$$$-й и $$$4$$$-й. Вы получите строку 51, и это хорошая строка.
Во втором примере можно стереть все символы, кроме 0: оставшаяся строка 0000 — хорошая.
В третьем примере заданная строка $$$s$$$ уже является хорошей.
Название |
---|