Full lesson preview

Find the minimum palindrome partitioning cuts

Given a string, partition it into palindromic substrings and return the minimum number of cuts needed.

Python practice30 minDynamic ProgrammingAdvancedLast updated March 29, 2026

Problem statement

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum number of cuts needed to partition s into palindromic substrings. A cut is a division between two adjacent characters. For example, if s = "aab", one optimal partition is ["aa", "b"] which requires 1 cut. You should design an efficient algorithm using dynamic programming. Typical solutions run in O(n^2) time and O(n^2) space by precomputing a table of palindrome substrings and then computing minimum cuts for every prefix.

Task

Practice dynamic programming by precomputing palindromic substrings and using DP to compute minimum cuts.

Examples

Example 1

Input

aab

Output

Partition as ["aa", "b"] which requires 1 cut.

Input format

A single string s (may be empty).

Output format

An integer representing the minimum number of cuts needed.

Constraints

0 <= len(s) <= 2000. s consists of printable ASCII characters. Your solution should aim for O(n^2) time and O(n^2) space in the worst case.

Samples

Sample 1

Input

aab

Output

Split into "aa" | "b".