FunctionRacerProblemsRace

Fewest Cuts Into Palindromes

HardDynamic programmingPython, JavaScript, TypeScript, Java, C++

Cut text into pieces so that every piece reads the same forwards and backwards. Return the fewest cuts needed. If text is already a palindrome no cut is needed and the answer is 0; at worst you cut between every pair of neighboring characters, which takes len(text) - 1 cuts.

Example 1

text "aab"
returns 1

Cut into aa and b.

Example 2

text "noonabcba"
returns 1

Cut into noon and abcba.

Example 3

text "abc"
returns 2

No two neighboring characters form a palindrome, so every character must stand alone.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems