Дана строка $$$s$$$, состоящая из строчных латинских букв.
За одно действие вы можете выбрать несколько (одну или больше) позиций в ней так, что никакие две выбранные позиции не соседние друг другу. Затем вы удаляете все буквы на выбранных позициях из строки. Полученные части строки затем склеиваются без изменения порядка.
Какое наименьшее количество действий необходимо совершить, чтобы все буквы в строке $$$s$$$ стали одинаковые?
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В единственной строке каждого набора записана строка $$$s$$$, состоящая из строчных латинских букв. Ее длина от $$$1$$$ до $$$2 \cdot 10^5$$$.
Суммарная длина строк по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
На каждый набор входных данных выведите одно целое число — наименьшее количество действий, которые необходимо совершить, чтобы все буквы в строке $$$s$$$ стали одинаковые.
5abacabacodeforcesooooooooabcdefmewheniseearulhiiarul
1 3 0 2 4
В первом наборе входных данных вы можете выбрать позиции $$$2, 4$$$ и $$$6$$$, и удалить соответствующие буквы 'b', 'c' и 'b'.
В третьем примере все буквы в строке уже одинаковые, поэтому не нужно совершать никаких действий.
В четвертом примере одно из возможных решений за $$$2$$$ действия следующее. Сначала выбираете позиции $$$1, 4, 6$$$. Строка становится «bce». Затем выбираете позиции $$$1$$$ и $$$3$$$. Строка становится «c». Все буквы в ней одинаковые, так как это просто одна буква.
Название |
---|