#132

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Palindrome Partitioning II

Determine the minimum cuts required to partition a string into all palindromic substrings using dynamic programming techniques.

string dynamic programming

Problem Statement

Given a string s, partition s into substrings such that every substring is a palindrome. Your task is to compute the minimum number of cuts needed to achieve such a partitioning.

For example, given s = "aab", the optimal palindrome partitioning is ["aa","b"], which requires only one cut. Your solution must handle strings up to length 2000 consisting only of lowercase English letters.

Examples

Example 1

Input: s = "aab"

Output: 1

The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2

Input: s = "a"

Output: 0

Example details omitted.

Example 3

Input: s = "ab"

Output: 1

Example details omitted.

Constraints

1 <= s.length <= 2000
s consists of lowercase English letters only.

Solution Approach

Precompute Palindrome Table

Create a 2D boolean table isPalindrome[i][j] where each entry indicates whether the substring s[i..j] is a palindrome. This avoids repeated palindrome checks during dynamic programming and ensures state transitions can reference results in constant time.

Dynamic Programming Array

Define dp[i] as the minimum number of cuts needed for the substring s[0..i]. Initialize dp[0] = 0 and iterate over all possible end indices j. For each palindrome s[k..j], update dp[j] = min(dp[j], dp[k-1]+1), capturing the state transition pattern efficiently.

Optimization and Early Termination

If the entire substring s[0..j] is a palindrome, set dp[j] = 0 immediately to avoid unnecessary calculations. Combine the precomputed palindrome table with dynamic programming to reduce overall complexity and handle worst-case input efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) due to filling the palindrome table and updating dp for each substring. Space complexity is O(n^2) for the table and O(n) for dp, optimizing lookups for state transitions in dynamic programming.

What Interviewers Usually Probe

They may ask if you can precompute palindrome substrings to speed up checks.
Expect questions about how to handle overlapping subproblems efficiently.
They often probe understanding of the dp state definition and transitions.

Common Pitfalls or Variants

Common pitfalls

Failing to precompute palindromic substrings leads to TLE for longer inputs.
Incorrect dp initialization can cause off-by-one errors in cut counts.
Assuming single-pass greedy partitioning works ignores overlapping subproblems.

Follow-up variants

Return all possible palindrome partitions instead of the minimum cuts.
Handle strings with uppercase letters or special characters in palindrome checks.
Compute minimum cuts for palindromic substrings of a fixed maximum length.

FAQ

What is the main dynamic programming pattern in Palindrome Partitioning II?

The pattern is state transition dp where dp[i] represents minimum cuts for s[0..i] and updates depend on precomputed palindrome substrings.

Can I optimize space usage for this problem?

Yes, you can reduce the 2D palindrome table to a 1D array for checking palindromes on the fly, though it may complicate updates.

What is the time complexity for large strings?

Filling the palindrome table is O(n^2), and computing dp is also O(n^2), so overall complexity remains quadratic for worst-case inputs.

Why can't a greedy approach work here?

Greedy cuts fail because local palindrome decisions may prevent a globally minimal cut solution, requiring full dp state tracking.

Are single-character substrings always considered palindromes?

Yes, any single character is a palindrome, which simplifies base cases in the dp array and precomputed table.

terminal

Solution

Solution 1: Dynamic Programming

First, we preprocess the string $s$ to determine whether each substring $s[i..j]$ is a palindrome, and record this in a 2D array $g[i][j]$, where $g[i][j]$ indicates whether the substring $s[i..j]$ is a palindrome.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        g = [[True] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                g[i][j] = s[i] == s[j] and g[i + 1][j - 1]
        f = list(range(n))
        for i in range(1, n):
            for j in range(i + 1):
                if g[j][i]:
                    f[i] = min(f[i], 1 + f[j - 1] if j else 0)
        return f[-1]

Continue Practicing

#131 palindrome partitioning #139 word break #140 word break ii