Fewest Cuts Into Palindromes

Hard

You are given a string text. Cut it into pieces so that every piece is a palindrome, meaning it reads the same forwards and backwards. A single letter counts as a palindrome. Return the smallest number of cuts that achieves this.

Example 1

text='abacdc' → 1

One cut is enough: "aba" | "cdc".

Example 2

text='racecar' → 0

The whole string is already a palindrome, so no cuts are needed.

Example 3

text='xyzzy' → 1

"x" | "yzzy" takes a single cut.

Constraints

1 ≤ len(text) ≤ 2000
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

text='abacdc'

Expected

Run checks the first 3 tests in your browser. Submit checks all 161 tests on the server, hidden ones included.