LeetCode 132: Palindrome Partitioning II Solution in Python – A Step-by-Step Guide

What Is LeetCode 132: Palindrome Partitioning II?

In LeetCode 132: Palindrome Partitioning II, you’re given a string s, and your task is to find the minimum number of cuts required to partition it into substrings where each substring is a palindrome. A palindrome reads the same forward and backward (e.g., "racecar", "aa"). For example, with s = "aab", one cut after "aa" gives "aa" and "b" (both palindromes), so the output is 1. Unlike LeetCode 131, which lists all partitions, here we only need the minimum cut count.

Problem Statement

• Input: A string s.
• Output: An integer—the minimum number of cuts to make all substrings palindromes.
• Rules:
• Each substring in the partition must be a palindrome.
• Return the smallest number of cuts needed.

Constraints

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

Examples

• Input: s = "aab"
• Output: 1
• Why: Cut after "aa" → "aa", "b" (1 cut).
• Input: s = "a"
• Output: 0
• Why: Single character is a palindrome, no cuts needed.
• Input: s = "ab"
• Output: 1
• Why: Cut after "a" → "a", "b" (1 cut).

Understanding the Problem: Minimizing the Cuts

To solve LeetCode 132: Palindrome Partitioning II in Python, we need to determine the fewest cuts that split the string into palindrome substrings. A naive approach—trying all possible partitions like in LeetCode 131 and finding the minimum—would take O(2^n) time, which is too slow for a 2000-character string. Instead, we’ll use optimization:

• Best Solution (DP with Palindrome Precomputation): O(n²) time, O(n²) space—efficient and systematic.
• Alternative Solution (Two-Pointer with Greedy Cuts): O(n³) time, O(n) space—simpler but slower.

Let’s dive into the Best Solution—dynamic programming with palindrome precomputation—and break it down step-by-step.

Best Solution: Dynamic Programming with Palindrome Precomputation

Why This Is the Best Solution

The DP with palindrome precomputation approach is the top choice because it’s highly efficient—O(n²) time and O(n²) space—leveraging a precomputed palindrome table to minimize cuts quickly. It builds a DP array where each entry represents the minimum cuts needed up to that point, using palindrome checks to avoid redundant work. It’s like mapping out all possible palindrome pieces first, then finding the cheapest way to cut—smart and fast for the constraints!

How It Works

Here’s the strategy:

• Step 1: Precompute Palindromes:
• Build a 2D table is_palindrome[i][j] indicating if s[i:j+1] is a palindrome.
• Step 2: DP Array:
• dp[i]: Minimum cuts needed for s[0:i+1].
• Base case: dp[-1] = -1 (empty string needs -1 cuts to adjust for 0).
• Step 3: Fill DP:
• For each end index i:
• If s[0:i+1] is a palindrome, dp[i] = 0.
• Otherwise, try all cuts at j (0 to i-1), take min of dp[j] + 1 where s[j+1:i+1] is a palindrome.
• Step 4: Return:
• dp[n-1] is the minimum cuts for the whole string.

Step-by-Step Example

Example: s = "aab"

• Step 1: Precompute Palindromes:

a a b a T T F a T F b T

• Step 2: Initialize DP:
• dp = [-1, ?, ?] (n=3).
• Step 3: Fill DP:
• i = 0: "a" is palindrome, dp[0] = 0.
• i = 1: "aa" is palindrome, dp[1] = 0.
• i = 2: "aab" not palindrome:
• Cut at 0: "a" (dp[0]=0), "ab" (not palindrome), skip.
• Cut at 1: "aa" (dp[1]=0), "b" (palindrome), dp[2] = min(dp[2], dp[1] + 1) = 1.
• dp = [0, 0, 1].
• Result: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def minCut(self, s: str) -> int:
        n = len(s)

        # Step 1: Precompute palindrome table
        is_palindrome = [[False] * n for _ in range(n)]
        for i in range(n):
            is_palindrome[i][i] = True
        for length in range(2, n + 1):
            for start in range(n - length + 1):
                end = start + length - 1
                if s[start] == s[end] and (length == 2 or is_palindrome[start + 1][end - 1]):
                    is_palindrome[start][end] = True

        # Step 2: Initialize DP array
        dp = [float('inf')] * n
        dp.insert(0, -1)  # dp[-1] for empty string

        # Step 3: Fill DP
        for i in range(n):
            if is_palindrome[0][i]:
                dp[i] = 0
            else:
                for j in range(i):
                    if is_palindrome[j + 1][i]:
                        dp[i] = min(dp[i], dp[j] + 1)

        return dp[n - 1]

• Line 4: Get string length.
• Line 7-13: Build palindrome table:
• Line 8: Single characters are palindromes.
• Line 11-13: Check longer substrings.
• Line 16-17: Initialize DP with infinity, set base case.
• Line 20-25: Fill DP:
• Line 21-22: No cuts if whole prefix is palindrome.
• Line 24-25: Try cuts, minimize.
• Line 27: Return minimum cuts.
• Time Complexity: O(n²)—DP table and filling.
• Space Complexity: O(n²)—table size.

This is a cut-minimizing master!

Alternative Solution: Two-Pointer with Greedy Cuts

Why an Alternative Approach?

The two-pointer with greedy cuts approach offers a simpler, intuitive alternative—O(n³) time, O(n) space—using a greedy strategy to find cuts while checking palindromes on the fly. It’s less efficient but easier to conceptualize without precomputation. It’s like slicing the string step-by-step, always looking for the longest palindrome next—straightforward but slower.

How It Works

• Step 1: Use a DP array to track cuts.
• Step 2: Greedily find longest palindrome from start, cut, repeat.
• Step 3: Minimize cuts with two-pointer palindrome check.

Step-by-Step Example

Example: s = "aab"

• DP: [0, ?, ?] (base case 0 cuts for empty).
• i = 0: "a", dp[0] = 0.
• i = 1: "aa" (palindrome), dp[1] = 0.
• i = 2: "aab" not palindrome:
• "a" (dp[0]=0), "ab" (not palindrome).
• "aa" (dp[1]=0), "b" (palindrome), dp[2] = 1.
• Result: 1.

Code for Two-Pointer Approach

Copy codeclass Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        dp = [float('inf')] * n
        dp.insert(0, -1)

        def is_palindrome(left, right, s):
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

        for i in range(n):
            if is_palindrome(0, i, s):
                dp[i] = 0
            else:
                for j in range(i):
                    if is_palindrome(j + 1, i, s):
                        dp[i] = min(dp[i], dp[j] + 1)

        return dp[n - 1]

• Line 7-13: Two-pointer palindrome check.
• Line 16-21: Fill DP with greedy cuts.
• Time Complexity: O(n³)—n² cuts, n for palindrome check.
• Space Complexity: O(n)—DP array.

It’s a greedy slicer!

Comparing the Two Solutions

• DP with Precomputation (Best):
• Pros: O(n²) time, O(n²) space, fast and optimal.
• Cons: More space, setup complexity.
• Two-Pointer (Alternative):
• Pros: O(n³) time, O(n) space, simpler logic.
• Cons: Slower due to repeated checks.

DP wins for efficiency.

Additional Examples and Edge Cases

• "a": 0.
• "ababa": 1 ("aba", "ba").
• "abc": 2 ("a", "b", "c").

Both handle these well.

Complexity Breakdown

• DP: Time O(n²), Space O(n²).
• Two-Pointer: Time O(n³), Space O(n).

DP’s speed shines.

Key Takeaways

• DP: Precompute and optimize!
• Two-Pointer: Greedy cuts work!
• Cuts: Minimize with palindromes.
• Python Tip: DP arrays rule—see [Python Basics](/python/basics).

Final Thoughts: Slice to Win

LeetCode 132: Palindrome Partitioning II in Python is a string-cutting challenge. The DP approach minimizes cuts with precision, while two-pointer offers a simpler take. Want more palindrome fun? Try LeetCode 131: Palindrome Partitioning or LeetCode 5: Longest Palindromic Substring. Ready to cut? Head to Solve LeetCode 132 on LeetCode and minimize those slices today!