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

1
2
3

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2

1
2

Input: s = "a"
Output: 0

Example 3

1
2

Input: s = "ab"
Output: 1

Constraints

  • 1 <= s.length <= 2000
  • s consists 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

  1. Use a DP table dp[i][j] to record if s[i..j] is a palindrome.
  2. Use an array cut[j] to record the minimum cuts needed for s[0..j].
  3. For each end index j, try all start indices i <= j:
    • If s[i..j] is a palindrome, update cut[j]:
      • If i == 0, no cut needed.
      • Else, cut[j] = min(cut[j], cut[i-1] + 1).
  4. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

  1. Leetcode discussion - My solution does not need a table for palindrome, is it right ? It uses only O(n) space.

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”:

1
2
3

.......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]

1
2
3
4

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.
  1. GitHub - Tushar Roy