Palindrome Partitioning II

Hard Dynamic Programming Strings Original on LeetCode

Reported atGoogleAdobe

Palindrome Partitioning II is a hard dynamic programming problem solved with the strings pattern. The best approach, optimal (expand around centers), runs in O(n²) time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every palindromic first piece) up.

Problem

You are given a string s. Cut it into consecutive pieces so that every piece is a palindrome (reads the same forwards and backwards).

Return the minimum number of cuts needed. A string that is already a palindrome needs 0 cuts, and splitting into single characters always works, so the answer is at most s.length - 1.

Examples

Example 1

Input
s = "noonabc"
Output
3
Why
Split as "noon" | "a" | "b" | "c": four palindromes need three cuts, and no split with fewer pieces works.

Example 2

Input
s = "racecar"
Output
0
Why
The whole string is already a palindrome, so no cut is needed.

Example 3

Input
s = "abbab"
Output
1
Why
Split as "abba" | "b": two palindromes, one cut. The string itself is not a palindrome, so 0 is impossible.

Constraints

  • 1 <= s.length <= 2000
  • s consists of lowercase English letters only.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every palindromic first piece)O(n · 2^n)O(n)
Better (palindrome table + prefix DP)O(n²)O(n²)
Optimal (expand around centers)O(n²)O(n)

1Brute force (try every palindromic first piece)

TimeO(n · 2^n)There can be up to 2^(n-1) ways to split the string, and each palindrome check costs O(n).
SpaceO(n)The recursion depth is at most n.

Recursively pick the first piece: any palindromic prefix of the remaining string. Cut after it and solve the rest. The answer is the minimum over all choices. Without memoization the same suffix is solved again and again.

  1. solve(start): if s[start..] is itself a palindrome, return 0.
  2. Otherwise, for every end with s[start..end] a palindrome, try 1 + solve(end + 1).
  3. Return the minimum; the answer is solve(0).
class Solution {
    public int minCut(String s) {
        return solve(s, 0);
    }

    private int solve(String s, int start) {
        int n = s.length();
        if (isPal(s, start, n - 1)) return 0;
        int best = Integer.MAX_VALUE;
        for (int end = start; end < n - 1; end++) {
            if (isPal(s, start, end)) {
                best = Math.min(best, 1 + solve(s, end + 1));
            }
        }
        return best;
    }

    private boolean isPal(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) return false;
        }
        return true;
    }
}

2Better (palindrome table + prefix DP)

TimeO(n²)Filling the table and running the DP each look at every pair (j, i) once.
SpaceO(n²)The boolean table has n² cells.

First fill a table pal[i][j] telling whether s[i..j] is a palindrome: it is when the end characters match and the inside s[i+1..j-1] is a palindrome (or empty). Then compute dp[i], the fewest cuts for s[0..i], from left to right using the table.

  1. Fill pal for i from n - 1 down to 0 and j from i to n - 1: pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i+1][j-1]).
  2. For each i: if pal[0][i], dp[i] = 0.
  3. Otherwise dp[i] = min over j in 1..i with pal[j][i] of dp[j-1] + 1.
  4. Return dp[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++) {
                pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
            }
        }
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            if (pal[0][i]) {
                dp[i] = 0;
                continue;
            }
            int best = i;
            for (int j = 1; j <= i; j++) {
                if (pal[j][i]) best = Math.min(best, dp[j - 1] + 1);
            }
            dp[i] = best;
        }
        return dp[n - 1];
    }
}

3Optimal (expand around centers)

TimeO(n²)Each center expands at most n steps, and there are 2n - 1 centers.
SpaceO(n)Only the cuts array of length n + 1.

Skip the table. Let cuts[i] be the fewest cuts for the prefix of length i, with cuts[0] = -1 so that a prefix that is one whole palindrome gets 0. Expand outward from each of the 2n - 1 centers; every palindrome s[l..r] discovered this way can be the last piece of the prefix of length r + 1, so cuts[r+1] = min(cuts[r+1], cuts[l] + 1). Centers are processed left to right, and cuts[l] is final by the time it is read because l is at most the center.

  1. Initialize cuts[i] = i - 1 for i = 0..n (the all-single-characters split).
  2. For each center c from 0 to n - 1, expand odd palindromes (l = r = c) and even ones (l = c, r = c + 1).
  3. While l >= 0, r < n and s[l] == s[r]: set cuts[r+1] = min(cuts[r+1], cuts[l] + 1), then l--, r++.
  4. Return cuts[n].
class Solution {
    public int minCut(String s) {
        int n = s.length();
        int[] cuts = new int[n + 1];
        for (int i = 0; i <= n; i++) cuts[i] = i - 1;
        for (int c = 0; c < n; c++) {
            expand(s, c, c, cuts);
            expand(s, c, c + 1, cuts);
        }
        return cuts[n];
    }

    private void expand(String s, int l, int r, int[] cuts) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            cuts[r + 1] = Math.min(cuts[r + 1], cuts[l] + 1);
            l--;
            r++;
        }
    }
}

Edge cases to test

  • A single character needs 0 cuts
  • The whole string is a palindrome: answer 0
  • All characters distinct: answer is n - 1
  • Greedily taking the longest palindromic prefix can be wrong: for "aaba" it gives "aa" | "b" | "a" (2 cuts) while "a" | "aba" needs only 1

Hints

Hint 1

Let cuts[i] be the fewest cuts for the prefix of length i. The last piece of that prefix is some palindrome s[j..i-1], so cuts[i] = min over such j of cuts[j] + 1.

Hint 2

You need to know quickly whether s[j..i-1] is a palindrome. Precompute a table, or avoid the table altogether.

Hint 3

Expand around every center: each palindrome s[l..r] found while expanding gives the candidate cuts[r+1] = cuts[l] + 1, with cuts[0] = -1.

FAQ

What is the best time complexity for Palindrome Partitioning II?

Optimal (expand around centers) runs in O(n²) time and O(n) extra space. Each center expands at most n steps, and there are 2n - 1 centers.

Which pattern does Palindrome Partitioning II use?

It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Longest Palindromic Subsequence.

Is there a brute force solution for Palindrome Partitioning II?

Yes. Brute force (try every palindromic first piece) takes O(n · 2^n) time and O(n) space. Recursively pick the first piece: any palindromic prefix of the remaining string.

Which edge cases should I test for Palindrome Partitioning II?

A single character needs 0 cuts; The whole string is a palindrome: answer 0; All characters distinct: answer is n - 1; Greedily taking the longest palindromic prefix can be wrong: for "aaba" it gives "aa" | "b" | "a" (2 cuts) while "a" | "aba" needs only 1.