LeetCode 132 - Palindrome Partitioning II
The problem asks us to split a string into substrings such that every substring is a palindrome. Among all valid palindrome partitions, we must return the minimum number of cuts required. A cut divides the string into two parts.
Difficulty: 🔴 Hard
Topics: String, Dynamic Programming
Solution
Problem Understanding
The problem asks us to split a string into substrings such that every substring is a palindrome. Among all valid palindrome partitions, we must return the minimum number of cuts required.
A cut divides the string into two parts. For example, if the string is "aab", we can partition it as:
"a" | "a" | "b"which uses 2 cuts"aa" | "b"which uses 1 cut
Since "aa" is itself a palindrome, the second partition is better, so the answer is 1.
The input is a single string s consisting only of lowercase English letters. The length can be as large as 2000, which is an important constraint because it rules out highly exponential solutions. Any algorithm significantly worse than O(n^2) or O(n^3) will likely time out.
The output is a single integer representing the minimum number of cuts needed so that every resulting substring is a palindrome.
Several edge cases are important:
- A string that is already a palindrome, such as
"racecar", requires0cuts. - A string with no multi-character palindromes, such as
"abc", requiresn - 1cuts. - Very short strings like
"a"or"ab"are easy to mishandle if base cases are incorrect. - Repeated characters such as
"aaaaa"create many overlapping palindromic substrings, which makes memoization or dynamic programming especially important.
Approaches
Brute Force Approach
The brute force solution tries every possible way to partition the string and checks whether all resulting substrings are palindromes.
At each position, we can either cut or continue extending the current substring. This creates an exponential number of possible partitions. For every partition, we must validate whether each substring is a palindrome.
For example, for "aab":
"a" | "a" | "b""aa" | "b"
The brute force solution evaluates all possibilities and keeps the minimum number of cuts among valid partitions.
This approach is correct because it exhaustively explores every partition configuration. However, it is far too slow for n = 2000. The number of partitions grows exponentially, making this infeasible.
Key Insight for the Optimal Solution
The main observation is that many palindrome checks repeat.
Suppose we already know whether s[i:j] is a palindrome. Then we can reuse that information whenever we consider partitions involving that substring.
This naturally leads to dynamic programming.
The optimal solution uses two DP structures:
- A palindrome table
is_palindrome[i][j]
- Stores whether substring
s[i:j+1]is a palindrome. - Allows constant-time palindrome checks later.
- A cuts array
dp[i]
- Represents the minimum cuts needed for substring
s[0:i+1].
The recurrence works as follows:
-
If
s[0:i]itself is a palindrome, thendp[i] = 0. -
Otherwise, try every possible partition point
j. -
If
s[j:i]is a palindrome, then: -
dp[i] = min(dp[i], dp[j-1] + 1)
This transforms the exponential search into a polynomial-time dynamic programming solution.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n × n) | O(n) | Explores every partition recursively |
| Optimal | O(n^2) | O(n^2) | Uses palindrome preprocessing with DP |
Algorithm Walkthrough
Step 1: Create a palindrome lookup table
We create a 2D table is_palindrome where:
is_palindrome[i][j] = True
means substring s[i:j+1] is a palindrome.
This preprocessing is essential because repeatedly checking palindromes directly would increase the runtime significantly.
A substring is a palindrome if:
- The characters at both ends match
- The inner substring is also a palindrome
So:
s[i] == s[j] AND is_palindrome[i+1][j-1]
For substrings of length 1 or 2:
- Length 1 is always a palindrome
- Length 2 is a palindrome if both characters match
Step 2: Initialize the DP array
We create:
dp[i]
which stores the minimum cuts needed for substring s[0:i+1].
Initially, the worst case for position i is:
dp[i] = i
because we could cut between every character.
For example:
"abcd"
would require:
a | b | c | d
which uses 3 cuts.
Step 3: Fill the palindrome table while computing cuts
We iterate through every ending index end.
For each end, we examine all possible starting indices start.
If s[start:end+1] is a palindrome:
- Mark it in
is_palindrome - Update the minimum cuts
There are two cases:
- The palindrome starts at index
0
- No cuts are needed
dp[end] = 0
- The palindrome starts later
- Add one cut before this palindrome
- Candidate value becomes:
dp[start - 1] + 1
We take the minimum across all valid partitions.
Step 4: Return the final answer
The result is:
dp[n - 1]
because it represents the minimum cuts for the entire string.
Why it works
The algorithm works because every valid palindrome partition must end with some palindrome substring.
For every position end, we consider all palindrome substrings ending there. If we know the optimal solution for everything before that substring, then adding one cut produces a valid candidate solution.
Dynamic programming guarantees optimality because each state is built from smaller optimal subproblems.
Python Solution
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
# is_palindrome[i][j] tells whether s[i:j+1] is a palindrome
is_palindrome = [[False] * n for _ in range(n)]
# dp[i] = minimum cuts needed for s[0:i+1]
dp = [0] * n
for end in range(n):
# Worst case: cut before every character
dp[end] = end
for start in range(end + 1):
if (
s[start] == s[end]
and (
end - start <= 2
or is_palindrome[start + 1][end - 1]
)
):
is_palindrome[start][end] = True
# Entire substring is a palindrome
if start == 0:
dp[end] = 0
else:
dp[end] = min(dp[end], dp[start - 1] + 1)
return dp[-1]
The implementation combines palindrome detection and minimum-cut computation into a single nested loop structure.
The outer loop iterates over every possible ending position of a substring. For each ending position, we initialize the worst-case number of cuts.
The inner loop tries every possible starting position. Whenever a palindrome is found, we update the palindrome table so future computations can reuse it efficiently.
If the palindrome begins at index 0, then no cuts are necessary because the entire prefix is already valid. Otherwise, we add one cut before the palindrome and compare against the current best value.
This approach avoids recomputing palindromes and ensures that every substring is processed efficiently.
Go Solution
func minCut(s string) int {
n := len(s)
isPalindrome := make([][]bool, n)
for i := range isPalindrome {
isPalindrome[i] = make([]bool, n)
}
dp := make([]int, n)
for end := 0; end < n; end++ {
// Worst case: cut before every character
dp[end] = end
for start := 0; start <= end; start++ {
if s[start] == s[end] &&
(end-start <= 2 || isPalindrome[start+1][end-1]) {
isPalindrome[start][end] = true
if start == 0 {
dp[end] = 0
} else {
dp[end] = min(dp[end], dp[start-1]+1)
}
}
}
}
return dp[n-1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
The Go implementation closely mirrors the Python version, but there are some language-specific details.
Go does not provide a built-in min function for integers, so we define one manually.
The palindrome table is created as a slice of slices. Each row must be allocated individually.
Strings in Go are byte-indexable, which works correctly here because the problem guarantees lowercase English letters only. If Unicode characters were possible, indexing would require rune conversion.
Worked Examples
Example 1
Input:
s = "aab"
Initial State
| Index | Character |
|---|---|
| 0 | a |
| 1 | a |
| 2 | b |
Initial DP:
| i | dp[i] |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
Processing end = 0
Substring:
"a"
Palindrome found.
| start | end | substring | palindrome | dp |
|---|---|---|---|---|
| 0 | 0 | a | Yes | dp[0] = 0 |
Processing end = 1
Check substrings ending at index 1.
| start | substring | palindrome | dp update |
|---|---|---|---|
| 0 | aa | Yes | dp[1] = 0 |
| 1 | a | Yes | min(0, dp[0] + 1) = 0 |
Current DP:
| i | dp[i] |
|---|---|
| 0 | 0 |
| 1 | 0 |
| 2 | 2 |
Processing end = 2
| start | substring | palindrome | dp update |
|---|---|---|---|
| 0 | aab | No | none |
| 1 | ab | No | none |
| 2 | b | Yes | dp[2] = dp[1] + 1 = 1 |
Final DP:
| i | dp[i] |
|---|---|
| 0 | 0 |
| 1 | 0 |
| 2 | 1 |
Answer:
1
Example 2
Input:
s = "a"
Single-character strings are always palindromes.
| end | substring | dp |
|---|---|---|
| 0 | a | 0 |
Answer:
0
Example 3
Input:
s = "ab"
Processing
| substring | palindrome |
|---|---|
| a | Yes |
| b | Yes |
| ab | No |
Partition:
a | b
requires 1 cut.
Answer:
1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n^2) | Every pair (start, end) is processed once |
| Space | O(n^2) | The palindrome lookup table stores all substring states |
The nested loops iterate over all possible substring boundaries, resulting in O(n^2) operations.
The palindrome table also requires O(n^2) memory because we store a boolean value for every substring.
Although the space usage is relatively large, it is acceptable for n <= 2000.
Test Cases
sol = Solution()
assert sol.minCut("aab") == 1 # Basic example with one optimal cut
assert sol.minCut("a") == 0 # Single character
assert sol.minCut("ab") == 1 # No multi-character palindrome
assert sol.minCut("aa") == 0 # Entire string is palindrome
assert sol.minCut("aba") == 0 # Odd-length palindrome
assert sol.minCut("abba") == 0 # Even-length palindrome
assert sol.minCut("abc") == 2 # Every character separated
assert sol.minCut("aabb") == 1 # "aa | bb"
assert sol.minCut("banana") == 1 # "b | anana"
assert sol.minCut("cdd") == 1 # "c | dd"
assert sol.minCut("aaaaa") == 0 # Repeated characters
assert sol.minCut("abcdef") == 5 # Worst-case cutting
assert sol.minCut("racecar") == 0 # Large palindrome
assert sol.minCut("aabaa") == 0 # Nested palindrome
assert sol.minCut("noonabbad") == 2 # "noon | abba | d"
| Test | Why |
|---|---|
"aab" |
Validates basic partitioning |
"a" |
Smallest possible input |
"ab" |
No palindrome longer than 1 |
"aa" |
Two-character palindrome |
"aba" |
Odd-length palindrome |
"abba" |
Even-length palindrome |
"abc" |
Maximum cuts needed |
"aabb" |
Multiple palindrome groups |
"banana" |
Large internal palindrome |
"cdd" |
Palindrome at the end |
"aaaaa" |
Repeated characters |
"abcdef" |
Worst-case partitioning |
"racecar" |
Entire string palindrome |
"aabaa" |
Nested palindrome structure |
"noonabbad" |
Multiple large palindromes |
Edge Cases
Single Character Strings
A string like "a" requires zero cuts because a single character is always a palindrome.
This case is important because incorrect initialization can accidentally produce 1 instead of 0. The implementation handles this by setting dp[end] = 0 whenever the palindrome begins at index 0.
Strings With No Large Palindromes
Strings such as "abcdef" contain no palindrome longer than one character.
In this situation, the algorithm should produce n - 1 cuts. The implementation naturally handles this because the only valid palindromes discovered are single-character substrings.
Entire String Already a Palindrome
For inputs like "racecar" or "abba", the correct answer is 0.
This case can be mishandled if the algorithm always assumes at least one cut is required. The implementation correctly detects when the substring from 0 to end is a palindrome and immediately sets dp[end] = 0.
Repeated Characters
Strings like "aaaaaa" contain many overlapping palindromes.
Naive recursive solutions perform poorly here because they repeatedly recompute the same palindrome checks. The DP palindrome table eliminates redundant work by storing previously computed results.