Statement is not available in English language
B. Удали символы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$, состоящая из строчных латинских букв. За один ход можно удалить из строки две буквы, если они равны и находятся на одинаковом расстоянии от концов строки. Формально, можно удалить символы $$$s_i$$$ и $$$s_j$$$, если:

  • $$$s_i = s_j$$$
  • $$$|i - 1| = |n - j|$$$, где $$$n$$$ — длина строки перед удалением
  • $$$i \neq j$$$

Необходимо определить минимально возможную длину строки, которую можно получить после последовательности таких операций.

Входные данные

Первая строка содержит строку $$$s$$$ ($$$1 \le |s| \le 10^5$$$), состоящую из строчных латинских букв.

$$$|s|$$$ обозначает длину строки $$$s$$$.

Выходные данные

Выведите одно целое число — минимально возможную длину строки после всех возможных удалений.

Система оценки

Тесты в этой задаче разбиты на 5 групп. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.

ПодзадачаБаллыДоп. ограниченияНеобх. подзадачи
13$$$|s| = 3$$$—
210Строка состоит из одинаковых букв—
320$$$|s| \le 100$$$—
431$$$|s| \le 1000$$$3
536—1-4
Примеры
Входные данные
abba
Выходные данные
0
Входные данные
abcde
Выходные данные
5
Входные данные
aabaa
Выходные данные
1
Примечание

В первом примере можно удалить все символы:

  • Удаляем $$$s_1$$$ и $$$s_4$$$ (оба 'a'), остается "bb"
  • Удаляем $$$s_1$$$ и $$$s_2$$$ (оба 'b'), строка пуста

Во втором примере нельзя удалить ни одну пару символов.

В третьем примере можно удалить пары 'a' с обоих концов, оставив только центральный символ.