Palindrome Partitioning II
Description
You are given a string s consisting of lowercase English letters. Your task is to partition this string into substrings such that every substring in the partition is a palindrome (reads the same forwards and backwards).
Return the minimum number of cuts needed to achieve such a palindrome partitioning.
A single character is always a palindrome, so a valid partitioning always exists — in the worst case, you cut between every pair of adjacent characters, making each substring a single character. The challenge is to minimize the number of cuts.
Examples
Example 1
Input: s = "aab"
Output: 1
Explanation: One cut produces the partition ["aa", "b"]. Both "aa" and "b" are palindromes. We cannot achieve zero cuts because the entire string "aab" is not a palindrome. Therefore, 1 is the minimum number of cuts.
Example 2
Input: s = "a"
Output: 0
Explanation: The string "a" is already a palindrome by itself. No cuts are needed.
Example 3
Input: s = "ab"
Output: 1
Explanation: "ab" is not a palindrome. The only valid partitioning is ["a", "b"], which requires 1 cut.
Constraints
- 1 ≤ s.length ≤ 2000
- s consists of lowercase English letters only
Editorial
Brute Force
Intuition
The most natural starting point is to consider every possible way to place a cut in the string. Think of it like slicing a loaf of bread — you can cut it at any position, and for each piece you get, you check if it reads the same forwards and backwards. If a piece is not a palindrome, you need to cut that piece further.
Formally, we define a recursive function solve(i, j) that returns the minimum cuts needed to partition the substring s[i..j] into palindromes.
The logic is:
- If
s[i..j]is already a palindrome, no cuts are needed — return 0. - Otherwise, try every possible cut position
kbetweeniandj-1. Each cut splits the string into two parts:s[i..k]ands[k+1..j]. We recursively find the minimum cuts for each part and add 1 for the cut itself. - Return the minimum over all cut positions.
This is similar to the Matrix Chain Multiplication pattern — we try all possible split points and pick the best one.
Step-by-Step Explanation
Let's trace with s = "aab".
Step 1: Call solve(0, 2) for the entire string "aab". Is "aab" a palindrome? s[0]='a' vs s[2]='b' — no. We must try cuts.
Step 2: Try cut at k=0. This splits into "a" (solve(0,0)) and "ab" (solve(1,2)). We need to solve both parts.
Step 3: solve(0, 0) — substring "a". A single character is always a palindrome. Return 0.
Step 4: solve(1, 2) — substring "ab". Is "ab" a palindrome? s[1]='a' vs s[2]='b' — no. Try cuts.
Step 5: The only cut position in solve(1,2) is k=1. This splits into "a" (solve(1,1)) and "b" (solve(2,2)).
Step 6: solve(1, 1) = 0 (single char "a"). solve(2, 2) = 0 (single char "b").
Step 7: solve(1, 2) = solve(1,1) + 1 + solve(2,2) = 0 + 1 + 0 = 1. So "ab" needs 1 cut: "a|b".
Step 8: Back to the first cut option: solve(0,0) + 1 + solve(1,2) = 0 + 1 + 1 = 2. Cutting after position 0 costs 2 total cuts: "a|a|b".
Step 9: Try cut at k=1 in solve(0,2). This splits into "aa" (solve(0,1)) and "b" (solve(2,2)).
Step 10: solve(0, 1) — substring "aa". Is it a palindrome? s[0]='a' == s[1]='a' — yes! Return 0.
Step 11: solve(2, 2) = 0 (single char).
Step 12: Second cut option: solve(0,1) + 1 + solve(2,2) = 0 + 1 + 0 = 1. Cutting after position 1 costs 1 cut: "aa|b".
Step 13: solve(0, 2) = min(2, 1) = 1. The answer is 1.
Brute Force Recursion — Trying All Cut Positions — Watch the recursion explore every possible cut position in "aab". Each node represents a subproblem solve(i,j). Leaf nodes are palindromes requiring 0 cuts.
Algorithm
- Define a helper isPalindrome(s, i, j) that checks if s[i..j] reads the same forwards and backwards.
- Define solve(s, i, j) returning the minimum cuts for s[i..j]:
- If i ≥ j or isPalindrome(s, i, j), return 0 (no cuts needed).
- For each k from i to j-1:
- Compute cuts = solve(s, i, k) + 1 + solve(s, k+1, j)
- Track the minimum.
- Return the minimum.
- Return solve(s, 0, n-1).
Code
#include <string>
#include <climits>
using namespace std;
class Solution {
public:
bool isPalindrome(string& s, int i, int j) {
while (i < j) {
if (s[i] != s[j]) return false;
i++; j--;
}
return true;
}
int solve(string& s, int i, int j) {
if (i >= j || isPalindrome(s, i, j)) return 0;
int minCuts = INT_MAX;
for (int k = i; k < j; k++) {
int cuts = solve(s, i, k) + 1 + solve(s, k + 1, j);
minCuts = min(minCuts, cuts);
}
return minCuts;
}
int minCut(string s) {
return solve(s, 0, s.size() - 1);
}
};class Solution:
def minCut(self, s: str) -> int:
def is_palindrome(i, j):
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
def solve(i, j):
if i >= j or is_palindrome(i, j):
return 0
min_cuts = float('inf')
for k in range(i, j):
cuts = solve(i, k) + 1 + solve(k + 1, j)
min_cuts = min(min_cuts, cuts)
return min_cuts
return solve(0, len(s) - 1)class Solution {
private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if (s.charAt(i) != s.charAt(j)) return false;
i++; j--;
}
return true;
}
private int solve(String s, int i, int j) {
if (i >= j || isPalindrome(s, i, j)) return 0;
int minCuts = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cuts = solve(s, i, k) + 1 + solve(s, k + 1, j);
minCuts = Math.min(minCuts, cuts);
}
return minCuts;
}
public int minCut(String s) {
return solve(s, 0, s.length() - 1);
}
}Complexity Analysis
Time Complexity: O(n × 2^n)
For a string of length n, there are n-1 possible cut positions, giving 2^(n-1) possible ways to partition the string. For each partition, we also call isPalindrome which takes O(n). The exact complexity is difficult to express tightly, but a loose upper bound is O(n × 2^n). For n = 2000, this is astronomically large.
Space Complexity: O(n)
The recursion stack depth is at most n (when every cut produces a single character on one side). Each stack frame uses O(1) additional space. The isPalindrome call uses O(1) space.
Why This Approach Is Not Efficient
The brute force has exponential time complexity. With n up to 2000, 2^2000 is an incomprehensibly large number — far beyond any feasible computation.
The core problem is overlapping subproblems. The same substring s[i..j] is evaluated multiple times via different cut sequences. For instance, in our trace of "aab", solve(2,2) was computed twice — once inside solve(1,2) and once directly from solve(0,2).
For longer strings, this redundancy explodes. The subproblem solve(i,j) depends only on the indices i and j, and there are only O(n²) unique (i,j) pairs. If we store the result the first time we compute each pair and reuse it thereafter, we avoid all redundant computation. This leads us to memoization.
Better Approach - Memoization (Top-Down DP)
Intuition
We use the exact same recursive logic as brute force but add a 2D cache table dp[i][j]. Before computing solve(i, j), we check if the result is already stored. If yes, we return it instantly. If not, we compute it, save it in the cache, then return.
This transforms the exponential recursion into a polynomial one. There are at most n² unique (i,j) subproblems. For each subproblem, we try O(n) cut positions, and each isPalindrome check takes O(n) time. Total: O(n² × n) = O(n³) for the DP computation, plus O(n) per palindrome check.
The recurrence is identical to brute force — the only difference is the memo table that prevents recomputation.
Step-by-Step Explanation
Let's trace with s = "aab" using memoization.
Step 1: Call solve(0, 2). Check memo[0][2] → empty. "aab" not palindrome. Try cuts.
Step 2: k=0: Need solve(0,0). Check memo[0][0] → empty. "a" is palindrome → 0. Store memo[0][0] = 0.
Step 3: Need solve(1,2). Check memo[1][2] → empty. "ab" not palindrome. Try cuts.
Step 4: k=1 inside solve(1,2): Need solve(1,1) and solve(2,2). Both palindromes → 0. Store memo[1][1]=0 and memo[2][2]=0.
Step 5: solve(1,2) = 0 + 1 + 0 = 1. Store memo[1][2] = 1.
Step 6: First cut path: 0 + 1 + 1 = 2. Record min_cuts = 2.
Step 7: k=1: Need solve(0,1). Check memo[0][1] → empty. "aa" is palindrome → 0. Store memo[0][1] = 0.
Step 8: Need solve(2,2). Check memo[2][2] → FOUND: 0! This is a memo hit — we skip the computation entirely.
Step 9: Second cut: 0 + 1 + 0 = 1. Update min_cuts = min(2, 1) = 1.
Step 10: solve(0,2) = 1. Store memo[0][2] = 1. Answer = 1.
With memoization, we computed each unique subproblem exactly once. The memo hit on solve(2,2) saved us from redundant work.
Memoization — Caching Palindrome Partition Subproblems — Watch how the memo table stores results and avoids recomputation. When solve(2,2) is needed the second time, it returns instantly from the cache.
Algorithm
- Create a 2D memo table dp[n][n] initialized to -1.
- Define solve(s, i, j, dp):
- If dp[i][j] ≠ -1, return dp[i][j] (cache hit).
- If i ≥ j or isPalindrome(s, i, j), return dp[i][j] = 0.
- Try all cuts k from i to j-1: cost = solve(i, k) + 1 + solve(k+1, j).
- dp[i][j] = minimum cost. Return it.
- Return solve(s, 0, n-1, dp).
Code
#include <string>
#include <vector>
#include <climits>
using namespace std;
class Solution {
public:
bool isPalindrome(string& s, int i, int j) {
while (i < j) {
if (s[i] != s[j]) return false;
i++; j--;
}
return true;
}
int solve(string& s, int i, int j, vector<vector<int>>& dp) {
if (dp[i][j] != -1) return dp[i][j];
if (i >= j || isPalindrome(s, i, j)) return dp[i][j] = 0;
int minCuts = INT_MAX;
for (int k = i; k < j; k++) {
int cuts = solve(s, i, k, dp) + 1 + solve(s, k + 1, j, dp);
minCuts = min(minCuts, cuts);
}
return dp[i][j] = minCuts;
}
int minCut(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, -1));
return solve(s, 0, n - 1, dp);
}
};class Solution:
def minCut(self, s: str) -> int:
n = len(s)
dp = [[-1] * n for _ in range(n)]
def is_palindrome(i, j):
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
def solve(i, j):
if dp[i][j] != -1:
return dp[i][j]
if i >= j or is_palindrome(i, j):
dp[i][j] = 0
return 0
min_cuts = float('inf')
for k in range(i, j):
cuts = solve(i, k) + 1 + solve(k + 1, j)
min_cuts = min(min_cuts, cuts)
dp[i][j] = min_cuts
return min_cuts
return solve(0, n - 1)class Solution {
private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if (s.charAt(i) != s.charAt(j)) return false;
i++; j--;
}
return true;
}
private int solve(String s, int i, int j, int[][] dp) {
if (dp[i][j] != -1) return dp[i][j];
if (i >= j || isPalindrome(s, i, j)) return dp[i][j] = 0;
int minCuts = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cuts = solve(s, i, k, dp) + 1 + solve(s, k + 1, j, dp);
minCuts = Math.min(minCuts, cuts);
}
return dp[i][j] = minCuts;
}
public int minCut(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int[] row : dp) java.util.Arrays.fill(row, -1);
return solve(s, 0, n - 1, dp);
}
}Complexity Analysis
Time Complexity: O(n³)
There are O(n²) unique (i, j) subproblems. For each subproblem, we iterate over O(n) cut positions. The isPalindrome check inside takes O(n) time but is called once per subproblem (at the start, before trying cuts). So overall: O(n²) subproblems × O(n) cut positions = O(n³).
Space Complexity: O(n²)
The 2D memo table has n × n entries. The recursion stack depth is at most O(n). Dominant term: O(n²) for the table.
Why This Approach Is Not Efficient
While memoization reduces the exponential brute force to O(n³), this is still not fast enough for the given constraints. With n up to 2000, O(n³) = 8 × 10⁹ operations — well beyond the typical time limit of ~10⁸ operations per second.
The bottleneck comes from two sources:
- 2D state space: We define subproblems as (i, j) — start and end of a substring. This gives n² states, each requiring O(n) work.
- Redundant palindrome checks: Each isPalindrome(i, j) call takes O(n) and may be repeated.
Key insight for optimization: Instead of thinking about arbitrary substrings s[i..j], we can reformulate using a 1D DP. Define dp[i] = minimum cuts for the prefix s[0..i]. This gives us only n states instead of n². To evaluate dp[i], we check which suffixes s[j..i] are palindromes and take dp[i] = min(dp[j-1] + 1). If we precompute a palindrome lookup table isPalin[i][j] in O(n²), then each dp[i] needs at most O(n) suffix checks, giving O(n²) total — a full order of magnitude faster.
Optimal Approach - 1D DP with Palindrome Precomputation
Intuition
The key reformulation is to think about the problem from left to right. Instead of considering arbitrary substrings s[i..j], we ask: "What is the minimum number of cuts to partition the prefix s[0..i] into palindromes?"
Define dp[i] = minimum cuts for s[0..i]. The answer is dp[n-1].
Base case: If the entire prefix s[0..i] is itself a palindrome, dp[i] = 0 (no cuts needed).
Recurrence: Otherwise, we look for palindromic suffixes. If s[j..i] is a palindrome for some j ≥ 1, then we can cut right before position j. The cost is dp[j-1] + 1 (minimum cuts for the prefix before the cut, plus the cut itself). We take the minimum over all valid j.
To make palindrome checks O(1), we precompute isPalin[i][j] — a boolean table where isPalin[i][j] = true if and only if s[i..j] is a palindrome. This table can be built in O(n²) using the classic expansion approach: single characters are palindromes, and s[i..j] is a palindrome if s[i] == s[j] and s[i+1..j-1] is a palindrome.
With O(1) palindrome lookups, filling each dp[i] takes O(n) work (scanning all possible j), and we have n entries. Total: O(n²) — fast enough for n = 2000.
Step-by-Step Explanation
Let's trace with s = "aab" (n = 3).
Step 1: Precompute isPalin table.
- Single characters: isPalin[0][0]="a" ✓, isPalin[1][1]="a" ✓, isPalin[2][2]="b" ✓
- Length 2: isPalin[0][1]="aa" → s[0]='a'==s[1]='a' ✓. isPalin[1][2]="ab" → s[1]='a'≠s[2]='b' ✗.
- Length 3: isPalin[0][2]="aab" → s[0]='a'≠s[2]='b' ✗.
Step 2: Initialize dp = [∞, ∞, ∞].
Step 3: Compute dp[0]. Is s[0..0]="a" a palindrome? isPalin[0][0] = true → dp[0] = 0. No cuts needed for a single character.
Step 4: Compute dp[1]. Is s[0..1]="aa" a palindrome? isPalin[0][1] = true → dp[1] = 0. The whole prefix "aa" is a palindrome — no cuts!
Step 5: Compute dp[2]. Is s[0..2]="aab" a palindrome? isPalin[0][2] = false. Must check palindromic suffixes.
Step 6: Check j=1: Is s[1..2]="ab" a palindrome? isPalin[1][2] = false. Skip — cannot cut here.
Step 7: Check j=2: Is s[2..2]="b" a palindrome? isPalin[2][2] = true! Cut before position 2: dp[2] = dp[1] + 1 = 0 + 1 = 1. The partition is "aa" | "b".
Step 8: dp[2] = 1. Answer = dp[n-1] = dp[2] = 1.
1D DP — Minimum Palindrome Partition Cuts — Watch how dp[i] is filled left-to-right. For each position, we either find the whole prefix is a palindrome (0 cuts) or scan for the best palindromic suffix to cut before.
Algorithm
- Precompute palindrome table: Create isPalin[n][n].
- All single characters: isPalin[i][i] = true.
- For lengths 2 to n: isPalin[i][j] = (s[i] == s[j]) and (length == 2 or isPalin[i+1][j-1]).
- Fill DP array: Create dp[n] initialized to ∞.
- For each i from 0 to n-1:
- If isPalin[0][i], set dp[i] = 0 (whole prefix is palindrome).
- Otherwise, for each j from 1 to i:
- If isPalin[j][i], update dp[i] = min(dp[i], dp[j-1] + 1).
- For each i from 0 to n-1:
- Return dp[n-1].
Code
#include <string>
#include <vector>
#include <climits>
using namespace std;
class Solution {
public:
int minCut(string s) {
int n = s.size();
// Precompute palindrome table
vector<vector<bool>> isPalin(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) isPalin[i][i] = true;
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s[i] == s[j]) {
isPalin[i][j] = (len == 2) || isPalin[i + 1][j - 1];
}
}
}
// dp[i] = min cuts for s[0..i]
vector<int> dp(n, INT_MAX);
for (int i = 0; i < n; i++) {
if (isPalin[0][i]) {
dp[i] = 0;
} else {
for (int j = 1; j <= i; j++) {
if (isPalin[j][i]) {
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
}
}
return dp[n - 1];
}
};class Solution:
def minCut(self, s: str) -> int:
n = len(s)
# Precompute palindrome table
is_palin = [[False] * n for _ in range(n)]
for i in range(n):
is_palin[i][i] = True
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
is_palin[i][j] = (length == 2) or is_palin[i + 1][j - 1]
# dp[i] = min cuts for s[0..i]
dp = [float('inf')] * n
for i in range(n):
if is_palin[0][i]:
dp[i] = 0
else:
for j in range(1, i + 1):
if is_palin[j][i]:
dp[i] = min(dp[i], dp[j - 1] + 1)
return dp[n - 1]import java.util.Arrays;
class Solution {
public int minCut(String s) {
int n = s.length();
// Precompute palindrome table
boolean[][] isPalin = new boolean[n][n];
for (int i = 0; i < n; i++) isPalin[i][i] = true;
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j)) {
isPalin[i][j] = (len == 2) || isPalin[i + 1][j - 1];
}
}
}
// dp[i] = min cuts for s[0..i]
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
for (int i = 0; i < n; i++) {
if (isPalin[0][i]) {
dp[i] = 0;
} else {
for (int j = 1; j <= i; j++) {
if (isPalin[j][i]) {
dp[i] = Math.min(dp[i], dp[j - 1] + 1);
}
}
}
}
return dp[n - 1];
}
}Complexity Analysis
Time Complexity: O(n²)
The palindrome precomputation fills an n × n table by iterating over all substrings of increasing length. Each entry is computed in O(1) using previously computed entries. Total: O(n²).
The DP fills n entries. For each entry dp[i], we scan at most i suffix candidates, each requiring an O(1) isPalin lookup. In the worst case, the total work across all entries is O(n²) (sum of 1 + 2 + ... + n = n(n+1)/2).
Overall: O(n²) for palindrome table + O(n²) for DP = O(n²). With n = 2000, this is 4 × 10⁶ operations — extremely fast.
Space Complexity: O(n²)
The isPalin table requires n × n = O(n²) space. The dp array requires O(n). Dominant term: O(n²).