Ctrl K

Меньше всего разрезов

Сложная
Дана строка text. Её нужно разрезать на куски так, чтобы каждый кусок был палиндромом — читался одинаково слева направо и справа налево. Кусок из одной буквы тоже палиндром. Верните наименьшее число разрезов, которого для этого хватит.
Пример 1
text='abacdc' → 1

Один разрез: «aba» | «cdc».

Пример 2
text='racecar' → 0

Строка уже палиндром, резать не нужно.

Пример 3
text='xyzzy' → 1

«x» | «yzzy» — достаточно одного разреза.

Ограничения
  • 1 ≤ len(text) ≤ 2000
  • text состоит из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиШаблон с точкой и звёздочкой СложнаяСамый длинный сбалансированный отрезок скобок СложнаяПодходит ли строка под шаблон СложнаяПеретасовка разрезами СложнаяСколькими способами вычеркнуть Сложная
загружаем Python…
Вход
text='abacdc'
Ожидается
1

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 161 тест на сервере, включая скрытые.