We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Palindrome Partitioning II

Difficulty: Hard

Problem Description

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.

Key Insights

  • A palindrome reads the same backward as forward.
  • The problem can be solved using dynamic programming to minimize cuts.
  • We can use a 2D array to track whether substrings are palindromes.
  • A 1D array will keep track of the minimum cuts needed up to each index.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

We will use a dynamic programming approach where:

  1. We create a 2D boolean array isPalindrome to store whether a substring s[i:j] is a palindrome.
  2. We create a 1D array cuts where cuts[i] represents the minimum cuts needed for the substring s[0:i].
  3. For each index i, we check all possible substrings ending at i to determine if they are palindromes using the isPalindrome array.
  4. If a substring s[j:i] is a palindrome, then we can update the cuts needed based on previously computed values.

Code Solutions

def minCut(s: str) -> int:
    n = len(s)
    if n <= 1:
        return 0

    # Create a 2D array to store palindrome status
    isPalindrome = [[False] * n for _ in range(n)]
    
    # Initialize cuts array
    cuts = [0] * n
    
    for i in range(n):
        min_cuts = i  # Maximum cuts needed at worst is i (cutting each character)
        for j in range(i + 1):
            # Check if the substring s[j:i+1] is a palindrome
            if s[j] == s[i] and (i - j < 2 or isPalindrome[j + 1][i - 1]):
                isPalindrome[j][i] = True
                # If it's a palindrome, we can update min_cuts
                min_cuts = 0 if j == 0 else min(min_cuts, cuts[j - 1] + 1)
        cuts[i] = min_cuts
    
    return cuts[-1]
← Back to All Questions