Задачі
Разбиение на палиндромы
Разбиение на палиндромы
Разделение строки называется палиндромным разбиением, если каждая подстрока является палиндромом. Например, “aba|b|bbabb|a|b|aba” — это палиндромное разбиение “ababbbabbababa”.
Определите наименьшее количество разрезов, необходимых для палиндромного разбиения данной строки. Например, для “ababbbabbababa” требуется минимум 3 разреза. Они имеют вид: “a|babbbab|b|ababa”. Если строка уже является палиндромом, то ответом будет 0 разрезов. Если все символы строки длины n разные, то требуется минимум n - 1 разрезов.
Входные данные
Одна строка s длины не более 1000.
Выходные данные
Выведите минимальное количество разрезов, необходимых для палиндромного разбиения строки s.
Вхідні дані #1
abbaazxzazbxbz
Вихідні дані #1
2
Вхідні дані #2
abccba
Вихідні дані #2
0
Вхідні дані #3
qwerty
Вихідні дані #3
5