Palindrome partitioning II (min cuts)

Hard TimeO(n²) SpaceO(n²)

Cut a string so that every piece reads the same backwards, using as few cuts as possible. The cuts fall between characters and the pieces are contiguous. Cutting between every character always works, since a single character is a palindrome, so the question is how few will do — and a string that is already a palindrome needs none.

Examples

Example 1

Input
s = "aab"
Output
1
One cut gives aa and b, both palindromes; uncut, "aab" is not one.

Example 2

Input
s = "aba"
Output
0
"aba" already reads the same backwards, so no cut is needed at all.

The Code

function minCut(s) {
  const n = s.length;
  const isPal = [];
  for (let i = 0; i < n; i++) {
    isPal.push(new Array(n).fill(false));
  }
  for (let end = 0; end < n; end++) {
    for (let start = end; start >= 0; start--) {
      if (s[start] === s[end] && (end - start < 2 || isPal[start + 1][end - 1])) {
        isPal[start][end] = true;
      }
    }
  }
  const cuts = new Array(n).fill(0);
  for (let end = 0; end < n; end++) {
    if (isPal[0][end]) {
      cuts[end] = 0;
      continue;
    }
    let best = end;
    for (let start = 1; start <= end; start++) {
      if (isPal[start][end] && cuts[start - 1] + 1 < best) {
        best = cuts[start - 1] + 1;
      }
    }
    cuts[end] = best;
  }
  return cuts[n - 1];
}
minCut("aab");
Done

The first 19 calls, of 25. This one does not fit on a page.

Step through minCut("aab") call by call

More like this

All dynamic programming examples (20) →