AlgoInsight

DSA problem

Palindrome Partitioning II

HardString DPPattern: String DPtop300GoogleAmazonMicrosoftBloombergApple

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum number of cuts needed for a palindrome partitioning of s.

If the entire string is already a palindrome, the answer is 0. Otherwise we must find the smallest number of cut points that breaks s into palindromic pieces.

A brute force enumerates all possible partitions, then for each tests each piece for palindromicity. That is exponential and unusable for moderate n. We need a two-stage DP: precompute palindrome information in O(n^2), then use it to compute the minimum cuts in another O(n^2).

Step 1. Build a 2D boolean table pal[i][j] meaning "s[i..j] is a palindrome". Use the recurrence pal[i][j] = (s[i] == s[j]) && (j - i < 2 || pal[i+1][j-1]), filled by increasing length.

Step 2. Define dp[i] as the minimum cuts for s[0..i] (the prefix ending at index i). The recurrence: if pal[0][i] then dp[i] = 0; otherwise dp[i] = min(dp[j-1] + 1) over all j in [1..i] with pal[j][i] true.

Total cost: O(n^2) time, O(n^2) space for the palindrome table plus O(n) for cuts. A smarter expand-around-center version reduces space, but the canonical two-table approach is clearer.

Examples

Example 1
Input: s = "aab"
Output: 1
Explanation: One cut produces ["aa", "b"]. Both pieces are palindromes, so the minimum cut count is 1.
Example 2
Input: s = "a"
Output: 0
Explanation: A single character is already a palindrome; no cuts are needed.
Example 3
Input: s = "ab"
Output: 1
Explanation: One cut produces ["a", "b"], two single-character palindromes. No partition with zero cuts works because "ab" itself is not a palindrome.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

stringdynamic-programmingpalindrome

Browse all DSA problems