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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Palindrome Partitioning II

Number: 132

Difficulty: Hard

Paid? No

Companies: Google, Amazon

Problem Description

Given a string s, partition s such that every substring in the partition is a palindrome. Return the minimum number of cuts needed for a palindrome partitioning of s.

Key Insights

  • Precompute a 2D table (isPal) where isPal[i][j] indicates if the substring s[i...j] is a palindrome.
  • Use dynamic programming: dp[i] represents the minimum cuts needed for the substring s[0...i].
  • For every index i, iterate over all possible starting indices j. If s[j...i] is a palindrome, update dp[i] using dp[j-1] + 1 (or 0 if j is 0).
  • Time complexity is dominated by the O(n^2) palindrome checking and state transitions.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n^2) (due to the 2D table for palindrome checks, plus O(n) for the dp array)

Solution

The solution relies on dynamic programming with a two-step approach. First, precompute a 2D table (isPal) where each cell indicates if a substring is a palindrome. This is done in O(n^2) time by leveraging the fact that a substring s[j...i] is a palindrome if the characters at the ends match and the inner substring s[j+1...i-1] is also a palindrome (or if the length is less than 3).
Then, use a dp array where dp[i] holds the minimum number of cuts needed for the substring s[0...i]. For each i, check every index j (0 ≤ j ≤ i) and if s[j...i] is a palindrome, update dp[i] to be the minimum of its current value and dp[j-1] + 1 (with a special case when j is 0, meaning no cut is needed).
This two-phase approach efficiently breaks down the problem and computes the answer while avoiding redundant palindrome checks.

Code Solutions

Below are the implementations with line-by-line comments in multiple languages.

def minCut(s: str) -> int:
    n = len(s)
    # Precompute palindrome table where isPal[i][j] is True if s[i:j+1] is a palindrome.
    isPal = [[False] * n for _ in range(n)]
    # dp[i] will store the minimum cuts required for substring s[0...i]
    dp = [0] * n
    for i in range(n):
        min_cut = i  # maximum cuts (cut every character)
        for j in range(i + 1):
            # Check if s[j...i] is a palindrome:
            if s[j] == s[i] and (i - j < 2 or isPal[j+1][i-1]):
                isPal[j][i] = True  # Mark substring as palindrome.
                # If the palindrome starts at index 0, no cut is needed.
                min_cut = 0 if j == 0 else min(min_cut, dp[j-1] + 1)
        dp[i] = min_cut  # Record minimum cuts needed for s[0...i]
    return dp[-1]

# Example usage:
# print(minCut("aab"))  # Output: 1
← Back to All Questions