Palindrome Partitioning II
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 <= 2000sconsists 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(n · 2^n)There can be up to 2^(n-1) ways to split the string, and each palindrome check costs O(n).O(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.
- solve(start): if s[start..] is itself a palindrome, return 0.
- Otherwise, for every end with s[start..end] a palindrome, try 1 + solve(end + 1).
- 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;
}
}class Solution:
def minCut(self, s: str) -> int:
n = len(s)
def is_pal(l: int, r: int) -> bool:
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
def solve(start: int) -> int:
if is_pal(start, n - 1):
return 0
best = float("inf")
for end in range(start, n - 1):
if is_pal(start, end):
best = min(best, 1 + solve(end + 1))
return best
return solve(0)class Solution {
bool isPal(const string& s, int l, int r) {
while (l < r) {
if (s[l++] != s[r--]) return false;
}
return true;
}
int solve(const string& s, int start) {
int n = s.size();
if (isPal(s, start, n - 1)) return 0;
int best = INT_MAX;
for (int end = start; end < n - 1; end++) {
if (isPal(s, start, end)) {
best = min(best, 1 + solve(s, end + 1));
}
}
return best;
}
public:
int minCut(string s) {
return solve(s, 0);
}
};function minCut(s) {
const n = s.length;
const isPal = (l, r) => {
while (l < r) {
if (s[l++] !== s[r--]) return false;
}
return true;
};
const solve = (start) => {
if (isPal(start, n - 1)) return 0;
let best = Infinity;
for (let end = start; end < n - 1; end++) {
if (isPal(start, end)) {
best = Math.min(best, 1 + solve(end + 1));
}
}
return best;
};
return solve(0);
}2Better (palindrome table + prefix DP)
O(n²)Filling the table and running the DP each look at every pair (j, i) once.O(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.
- 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]).
- For each i: if pal[0][i], dp[i] = 0.
- Otherwise dp[i] = min over j in 1..i with pal[j][i] of dp[j-1] + 1.
- 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];
}
}class Solution:
def minCut(self, s: str) -> int:
n = len(s)
pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
dp = [0] * n
for i in range(n):
if pal[0][i]:
dp[i] = 0
continue
best = i
for j in range(1, i + 1):
if pal[j][i]:
best = min(best, dp[j - 1] + 1)
dp[i] = best
return dp[n - 1]class Solution {
public:
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++) {
pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1]);
}
}
vector<int> dp(n, 0);
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 = min(best, dp[j - 1] + 1);
}
dp[i] = best;
}
return dp[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++) {
pal[i][j] = s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1]);
}
}
const dp = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
if (pal[0][i]) {
dp[i] = 0;
continue;
}
let best = i;
for (let 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)
O(n²)Each center expands at most n steps, and there are 2n - 1 centers.O(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.
- Initialize cuts[i] = i - 1 for i = 0..n (the all-single-characters split).
- For each center c from 0 to n - 1, expand odd palindromes (l = r = c) and even ones (l = c, r = c + 1).
- While l >= 0, r < n and s[l] == s[r]: set cuts[r+1] = min(cuts[r+1], cuts[l] + 1), then l--, r++.
- 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++;
}
}
}class Solution:
def minCut(self, s: str) -> int:
n = len(s)
cuts = [i - 1 for i in range(n + 1)]
def expand(l: int, r: int) -> None:
while l >= 0 and r < n and s[l] == s[r]:
if cuts[l] + 1 < cuts[r + 1]:
cuts[r + 1] = cuts[l] + 1
l -= 1
r += 1
for c in range(n):
expand(c, c)
expand(c, c + 1)
return cuts[n]class Solution {
void expand(const string& s, int l, int r, vector<int>& cuts) {
int n = s.size();
while (l >= 0 && r < n && s[l] == s[r]) {
cuts[r + 1] = min(cuts[r + 1], cuts[l] + 1);
l--;
r++;
}
}
public:
int minCut(string s) {
int n = s.size();
vector<int> cuts(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];
}
};function minCut(s) {
const n = s.length;
const cuts = new Array(n + 1);
for (let i = 0; i <= n; i++) cuts[i] = i - 1;
const expand = (l, r) => {
while (l >= 0 && r < n && s[l] === s[r]) {
cuts[r + 1] = Math.min(cuts[r + 1], cuts[l] + 1);
l--;
r++;
}
};
for (let c = 0; c < n; c++) {
expand(c, c);
expand(c, c + 1);
}
return cuts[n];
}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.