Skills101
← All coding problems

Palindrome Partitioning — Minimum Cuts

mediumDynamic Programming II+20 XPTime limit 3s

Cut a word into pieces so that every piece is a palindrome. What is the minimum number of cuts needed? (A single letter is always a palindrome, so n − 1 cuts always work.)

Input: one line with the word.

Output: the minimum number of cuts.

Constraints: 1 ≤ length ≤ 1500; lowercase letters.

Example: aab → aa | b, 1 cut. abacdc → aba | cdc, 1 cut.

Think about it: cuts[i] = minimum cuts for the first i letters. If s[j..i−1] is a palindrome, cuts[i] can be cuts[j] + 1. Checking palindromes naively makes this O(n³); precompute them (a isPal[j][i] table) or expand around every centre to get O(n²).

Sample input 1

aab

Sample output 1

1

Sample input 2

abacdc

Sample output 2

1

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.