Дана строка \(s\), состоящая из строчных латинских букв.
За одно действие вы можете выбрать несколько (одну или больше) позиций в ней так, что никакие две выбранные позиции не соседние друг другу. Затем вы удаляете все буквы на выбранных позициях из строки. Полученные части строки затем склеиваются без изменения порядка.
Какое наименьшее количество действий необходимо совершить, чтобы все буквы в строке \(s\) стали одинаковые?
Выходные данные
На каждый набор входных данных выведите одно целое число — наименьшее количество действий, которые необходимо совершить, чтобы все буквы в строке \(s\) стали одинаковые.
Примечание
В первом наборе входных данных вы можете выбрать позиции \(2, 4\) и \(6\), и удалить соответствующие буквы 'b', 'c' и 'b'.
В третьем примере все буквы в строке уже одинаковые, поэтому не нужно совершать никаких действий.
В четвертом примере одно из возможных решений за \(2\) действия следующее. Сначала выбираете позиции \(1, 4, 6\). Строка становится «bce». Затем выбираете позиции \(1\) и \(3\). Строка становится «c». Все буквы в ней одинаковые, так как это просто одна буква.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
abacaba
codeforces
oooooooo
abcdef
mewheniseearulhiiarul
|
1
3
0
2
4
|