Palindrome Partitioning II

hard string dp

Problem

Given a string s, partition it so every substring is a palindrome. Return the minimum number of cuts needed.

Inputs = "aab"

Output1

"aa" | "b" — one cut splits s into two palindromes.

def min_cut(s):
    n = len(s)
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1]):
                pal[i][j] = True
    cuts = [0] * n
    for j in range(n):
        if pal[0][j]:
            cuts[j] = 0
        else:
            cuts[j] = min(cuts[i - 1] + 1 for i in range(1, j + 1) if pal[i][j])
    return cuts[n - 1]

function minCut(s) {
  const n = s.length;
  const pal = Array.from({ length: n }, () => new Array(n).fill(false));
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      if (s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1])) pal[i][j] = true;
    }
  }
  const cuts = new Array(n).fill(0);
  for (let j = 0; j < n; j++) {
    if (pal[0][j]) { cuts[j] = 0; continue; }
    let best = j;
    for (let i = 1; i <= j; i++) if (pal[i][j]) best = Math.min(best, cuts[i - 1] + 1);
    cuts[j] = best;
  }
  return cuts[n - 1];
}

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] pal = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1])) pal[i][j] = true;
            }
        }
        int[] cuts = new int[n];
        for (int j = 0; j < n; j++) {
            if (pal[0][j]) { cuts[j] = 0; continue; }
            int best = j;
            for (int i = 1; i <= j; i++) if (pal[i][j]) best = Math.min(best, cuts[i - 1] + 1);
            cuts[j] = best;
        }
        return cuts[n - 1];
    }
}

int minCut(string s) {
    int n = s.size();
    vector<vector<bool>> pal(n, vector<bool>(n, false));
    for (int i = n - 1; i >= 0; i--)
        for (int j = i; j < n; j++)
            if (s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1])) pal[i][j] = true;
    vector<int> cuts(n, 0);
    for (int j = 0; j < n; j++) {
        if (pal[0][j]) { cuts[j] = 0; continue; }
        int best = j;
        for (int i = 1; i <= j; i++) if (pal[i][j]) best = min(best, cuts[i - 1] + 1);
        cuts[j] = best;
    }
    return cuts[n - 1];
}

Explanation

This problem has two layers. First we need a fast way to ask "is the slice s[i..j] a palindrome?", and then we use those answers to find the fewest cuts. We solve the first part with a 2D table and the second with a 1D cuts array.

The table pal[i][j] is true when s[i..j] reads the same both ways. It is true when the two ends match (s[i] == s[j]) and the inside pal[i+1][j-1] is also a palindrome (or the slice is too short to have an inside). We fill i from right to left so the inner answer is ready before we need it.

Then cuts[j] is the minimum cuts for the prefix ending at j. If the whole prefix s[0..j] is already a palindrome, no cut is needed, so cuts[j] = 0. Otherwise we try every spot i where s[i..j] is a palindrome and take cuts[i-1] + 1 — one cut to break off that palindrome plus whatever the earlier part needed.

Example: s = "aab". Here "aa" is a palindrome and "b" is too, but the whole string is not. For the last character we cut after "aa", giving cuts = 1.

The answer is cuts[n-1], the minimum cuts to make the entire string into palindromes.

Time: O(n²) Space: O(n²)