Palindrome partitioning

Lesson · 10 min read · Dynamic programming · Palindrome partitioning

Cut a string into palindromes with the fewest cuts. Two tables: which pieces are palindromes, then the fewest pieces for each prefix.

Two DPs, one feeding the other

Cut aabcbd into pieces that are all palindromes, with as few cuts as possible: aa | bcb | d, two cuts. Think of the last piece: it is some palindrome s[j..i], and before it is the best partition of the prefix s[..j − 1].

Recurrence

pieces(i)

fewest palindromic pieces covering s[0..i] =
min over j ≤ i with s[j..i] a palindrome of pieces(j − 1) + 1, where pieces(−1) = 0.

answer

pieces(n − 1) − 1 cuts.

Testing "is s[j..i] a palindrome" inside the loop would cost O(n) each time. Precompute the palindrome table from the previous module first; then each test is a lookup and the whole algorithm is O(n²).

pieces(i) for aabcbd, using a precomputed palindrome table.

Step 1 / 6

s
a0a1b2c3b4d5
pieces
10·1·2·3·4·5
s[0..0]: best last piece "a", after nothing: 1 piece.
Step 2 / 6

s
a0a1b2c3b4d5
pieces
1011·2·3·4·5
s[0..1]: best last piece "aa", after nothing: 1 piece.
Step 3 / 6

s
a0a1b2c3b4d5
pieces
101122·3·4·5
s[0..2]: best last piece "b", after pieces(1) = 1: 2 pieces.
Step 4 / 6

s
a0a1b2c3b4d5
pieces
10112233·4·5
s[0..3]: best last piece "c", after pieces(2) = 2: 3 pieces.
Step 5 / 6

s
a0a1b2c3b4d5
pieces
1011223324·5
s[0..4]: best last piece "bcb", after pieces(1) = 1: 2 pieces.
Step 6 / 6

s
a0a1b2c3b4d5
pieces
101122332435
s[0..5]: best last piece "d", after pieces(4) = 2: 3 pieces. 3 pieces, so 2 cuts: aa | bcb | d.

Implementation

In six languages:

def min_cut(s):
    n = len(s)
    pal = [[False] * n for _ in range(n)]     # pal[j][i]: is s[j..i] a palindrome
    cuts = [0] * n                            # cuts[i]: fewest cuts for s[0..i]
    for i in range(n):
        best = i                              # cut between every character
        for j in range(i + 1):
            if s[j] == s[i] and (i - j < 3 or pal[j + 1][i - 1]):
                pal[j][i] = True
                best = 0 if j == 0 else min(best, cuts[j - 1] + 1)
        cuts[i] = best
    return cuts[n - 1]

#include <algorithm>
#include <string>
#include <vector>

int solve(std::string s) {
    const int n = s.size();
    std::vector<std::vector<bool>> pal(n, std::vector<bool>(n, false));
    std::vector<int> cuts(n, 0);
    for (int i = 0; i < n; ++i) {
        int best = i;
        for (int j = 0; j <= i; ++j)
            if (s[j] == s[i] && (i - j < 3 || pal[j + 1][i - 1])) {
                pal[j][i] = true;                         // s[j..i] is a palindrome
                best = j == 0 ? 0 : std::min(best, cuts[j - 1] + 1);
            }
        cuts[i] = best;
    }
    return cuts[n - 1];
}

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

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

fn solve(s: &str) -> i64 {
    let c: Vec<u8> = s.bytes().collect();
    let n = c.len();
    let mut pal = vec![vec![false; n]; n];
    let mut cuts = vec![0i64; n];
    for i in 0..n {
        let mut best = i as i64;
        for j in 0..=i {
            if c[j] == c[i] && (i - j < 3 || pal[j + 1][i - 1]) {
                pal[j][i] = true;                         // s[j..i] is a palindrome
                best = if j == 0 { 0 } else { best.min(cuts[j - 1] + 1) };
            }
        }
        cuts[i] = best;
    }
    cuts[n - 1]
}

import Data.Array

solve :: String -> Int
solve s = cuts ! (n - 1)
  where
    n = length s
    a = listArray (0, n - 1) s
    -- lazy tables: pal ! (j, i) and cuts ! i refer only to entries already defined in terms of smaller ones
    pal = array ((0, 0), (n - 1, n - 1)) [((j, i), j <= i && a ! j == a ! i && (i - j < 3 || pal ! (j + 1, i - 1))) | j <- [0 .. n - 1], i <- [0 .. n - 1]] :: Array (Int, Int) Bool
    cuts = listArray (0, n - 1) [best i | i <- [0 .. n - 1]] :: Array Int Int
    best i
      | pal ! (0, i) = 0
      | otherwise = minimum [cuts ! (j - 1) + 1 | j <- [1 .. i], pal ! (j, i)]

The same code is the reference solution to The fewest cuts into palindromes, where it is compiled and run against the tests in all six languages.

TimeO(n²)

SpaceO(n²) for the palindrome table

The table can be avoided by expanding around each centre and updating pieces at the right end of every palindrome found, which brings the memory down to O(n).