Войти Регистрация
Алгоритмы

86. Разрезать подпись на палиндромы

Сложная

В игре «Перевёртыши» в чатах VK подпись к стикеру режут на куски, каждый из которых читается одинаково слева направо и справа налево. Строка s — подпись из строчных латинских букв.

Верните минимальное число разрезов. Если вся подпись — палиндром, ответ 0.

В работе: Разбиение последовательности на симметричные блоки: разметка повторов в логах, сжатие зеркальных фрагментов.

Пример 1

Ввод
s = "abaab"
Вывод
1

«aba» | «ab» не годится, «a» | «baab» — один разрез.

Пример 2

Ввод
s = "abc"
Вывод
2

Каждая буква отдельно — два разреза.

Ограничения

  • 1 ≤ длина s ≤ 2000
  • s из строчных латинских букв
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def min_palindrome_cuts(s):
ДП на отрезкахПалиндромыРасширение от центрацельn2

Источник: наша задача на данных VK. Условие пересказано своими словами.