DSA Tracker

Visualize

Palindrome Partitioning II

dp[i] = min over palindromic suffixes s[j..i-1] of dp[j] + 1

time O(n^2)space O(n)

Every valid partition ends its LAST piece somewhere — say it starts at index j and runs to the end of the current prefix. If that piece is a palindrome, then the cuts needed for the whole prefix are exactly one more than the cuts needed for everything before it: dp[i] = dp[j] + 1. Trying every j and keeping the smallest result gives dp[i] = min cuts for the first i characters. The worst case (cut before every letter) is always available as a fallback, so dp[i] never has to stay unset.

Details

Animated on: Given string s = "aab", partition it so every piece is a palindrome. Return the minimum number of cuts needed.

Problem:Palindrome Partitioning IIHard

dp[i] = min over palindromic suffixes s[j..i-1] of dp[j] + 1

step 1 / 11

dp over "aab" — dp[i] = min cuts to partition the first i characters

dp[0] = -1: there's no prefix to cut yet, and this -1 is what makes "the whole prefix is itself a palindrome" cost 0 cuts once we add 1.

Pseudocode
1FUNCTION minCut(s):
2  n <- LENGTH(s)
3  isPal <- precomputed palindrome table for all s[i..j]
4  dp[0] <- -1
5  FOR i FROM 1 TO n:
6    dp[i] <- i - 1
7    FOR j FROM 0 TO i - 1:
8      IF isPal[j][i-1] = TRUE:
9        dp[i] <- MIN(dp[i], dp[j] + 1)
10  RETURN dp[n]

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. dp[0] = -1: there's no prefix to cut yet, and this -1 is what makes "the whole prefix is itself a palindrome" cost 0 cuts once we add 1.
  2. Worst case for "a": cut before every character but the first, 0 cuts. dp[1] starts at 0 and can only get smaller from here.
  3. "a" is a palindrome too, but dp[0] + 1 = 0 isn't better than the 0 already found — dp[1] stays 0.
  4. Worst case for "aa": cut before every character but the first, 1 cut. dp[2] starts at 1 and can only get smaller from here.
  5. "aa" reads the same both ways, so one cut after it plus dp[0] = -1 works: dp[2] = min(dp[2], -1 + 1) = 0.
  6. "a" is a palindrome too, but dp[1] + 1 = 1 isn't better than the 0 already found — dp[2] stays 0.
  7. Worst case for "aab": cut before every character but the first, 2 cuts. dp[3] starts at 2 and can only get smaller from here.
  8. "aab" isn't a palindrome, so a cut right after dp[0] wouldn't leave palindromic pieces — this split is skipped.
  9. "ab" isn't a palindrome, so a cut right after dp[1] wouldn't leave palindromic pieces — this split is skipped.
  10. "b" reads the same both ways, so one cut after it plus dp[2] = 0 works: dp[3] = min(dp[3], 0 + 1) = 1.
  11. dp[3] = 1 — "aab" needs only 1 cut to split into palindromes.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Palindrome Partitioning II in the editorAll Dynamic Programming problemsBack to roadmap