Palindrome Partitioning II
Problem
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Examples
Example 1
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 2
Input: s = "a"
Output: 0
Example 3
Input: s = "ab"
Output: 1
Constraints
1 <= s.length <= 2000sconsists of lowercase English letters only.
Solution
Method 1 - Dynamic Programming (Palindrome Cuts)
Intuition
We want to partition the string into the minimum number of cuts so that every substring is a palindrome. Dynamic programming helps us efficiently check all possible partitions and track the minimum cuts needed for each prefix.
Approach
- Use a DP table
dp[i][j]to record ifs[i..j]is a palindrome. - Use an array
cut[j]to record the minimum cuts needed fors[0..j]. - For each end index
j, try all start indicesi <= j:- If
s[i..j]is a palindrome, updatecut[j]:- If
i == 0, no cut needed. - Else,
cut[j] = min(cut[j], cut[i-1] + 1).
- If
- If
- Return
cut[n-1].
Complexity
- ⏰ Time complexity:
O(n^2)— Two nested loops over the string. - 🧺 Space complexity:
O(n^2)— DP table for palindromes and array for cuts.
Code
Java
class Solution {
public int minCut(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int[] cut = new int[n];
for (int j = 0; j < n; j++) {
cut[j] = j;
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i+1][j-1])) {
dp[i][j] = true;
if (i == 0) {
cut[j] = 0;
} else {
cut[j] = Math.min(cut[j], cut[i-1] + 1);
}
}
}
}
return cut[n-1];
}
}
Python
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
dp = [[False]*n for _ in range(n)]
cut = [i for i in range(n)]
for j in range(n):
for i in range(j+1):
if s[i] == s[j] and (j-i <= 1 or dp[i+1][j-1]):
dp[i][j] = True
if i == 0:
cut[j] = 0
else:
cut[j] = min(cut[j], cut[i-1]+1)
return cut[-1]
C++
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false));
vector<int> cut(n);
for (int j = 0; j < n; ++j) {
cut[j] = j;
for (int i = 0; i <= j; ++i) {
if (s[i] == s[j] && (j - i <= 1 || dp[i+1][j-1])) {
dp[i][j] = true;
if (i == 0) cut[j] = 0;
else cut[j] = min(cut[j], cut[i-1] + 1);
}
}
}
return cut[n-1];
}
};
Go
func minCut(s string) int {
n := len(s)
dp := make([][]bool, n)
for i := range dp {
dp[i] = make([]bool, n)
}
cut := make([]int, n)
for j := 0; j < n; j++ {
cut[j] = j
for i := 0; i <= j; i++ {
if s[i] == s[j] && (j-i <= 1 || dp[i+1][j-1]) {
dp[i][j] = true
if i == 0 {
cut[j] = 0
} else {
if cut[i-1]+1 < cut[j] {
cut[j] = cut[i-1]+1
}
}
}
}
}
return cut[n-1]
}
Kotlin
class Solution {
fun minCut(s: String): Int {
val n = s.length
val dp = Array(n) { BooleanArray(n) }
val cut = IntArray(n) { it }
for (j in 0 until n) {
for (i in 0..j) {
if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
dp[i][j] = true
if (i == 0) cut[j] = 0
else cut[j] = minOf(cut[j], cut[i - 1] + 1)
}
}
}
return cut[n - 1]
}
}
Rust
impl Solution {
pub fn min_cut(s: String) -> i32 {
let n = s.len();
let s = s.as_bytes();
let mut dp = vec![vec![false; n]; n];
let mut cut: Vec<i32> = (0..n as i32).collect();
for j in 0..n {
for i in 0..=j {
if s[i] == s[j] && (j - i <= 1 || dp[i+1][j-1]) {
dp[i][j] = true;
if i == 0 {
cut[j] = 0;
} else {
cut[j] = cut[j].min(cut[i-1] + 1);
}
}
}
}
cut[n-1]
}
}
TypeScript
class Solution {
minCut(s: string): number {
const n = s.length;
const dp: boolean[][] = Array.from({length: n}, () => Array(n).fill(false));
const cut: number[] = Array.from({length: n}, (_, i) => i);
for (let j = 0; j < n; j++) {
for (let i = 0; i <= j; i++) {
if (s[i] === s[j] && (j - i <= 1 || dp[i+1][j-1])) {
dp[i][j] = true;
if (i === 0) cut[j] = 0;
else cut[j] = Math.min(cut[j], cut[i-1] + 1);
}
}
}
return cut[n-1];
}
}
Notes
Explanation 1:
This divide-and-conquer algorithm utilize the symmetry of palindromes, so there is no need to cache the result of whether s[i:j] is a palindrome.
Say that it started at s[i] = 'b', and s[i-1,i+1] is a palindrome “aba”:
.......aba...
|<-X->| ^
|<---Y-->|
And we know the least cuts for s[0,i-1] is X, then the least cuts for s[0,i+1] Y is not greater than X+1. Last, we need to find out all the palindromes in s[0,i+1] so as to minimize the number of cuts.
Explanation 2:
The definition of ‘cut’ array is the minimum number of cuts of a sub string. More specifically, cut[n] stores the cut number of string s[0, n-1].
Here is the basic idea of the solution:
Initialize the ‘cut’ array: For a string with n characters s[0, n-1], it needs at most n-1 cut. Therefore, the ‘cut’ array is initialized as cut[i] = i-1
Use two variables in two loops to represent a palindrome:
The external loop variable ‘i’ represents the center of the palindrome. The internal loop variable ‘j’ represents the ‘radius’ of the palindrome. Apparently, j <= i is a must.
This palindrome can then be represented as s[i-j, i+j]. If this string is indeed a palindrome, then one possible value of cut[i+j] is cut[i-j] + 1, where cut[i-j] corresponds to s[0, i-j-1] and 1 correspond to the palindrome s[i-j, i+j];
When the loops finish, you’ll get the answer at cut[s.length]
if isPalindrome(i, j)
T[i][j] = 0;
else
T[i][j] = 1 + min(T[i][k] + T[k+1][j]) ; where k = i,..,j-1.