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 III

Number: 1403

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a string s consisting of lowercase letters and an integer k, the goal is to first change some characters of s (with minimum changes) and then partition the modified string into k non-empty disjoint substrings such that each substring is a palindrome. The task is to determine the minimal number of character changes required to achieve this.

Key Insights

  • Precompute the minimum changes needed to convert any substring s[i...j] into a palindrome.
  • Use dynamic programming (DP) where dp[i][p] represents the minimum changes required for the first i characters to form p palindromic substrings.
  • For the DP transition, consider partitioning the string at different indices and use the precomputed cost for converting the substring into a palindrome.
  • Base case: when there is only one partition (p = 1), the cost is exactly the precomputed cost for the whole substring.
  • The overall complexity is driven by the precomputation (O(n²)) and the DP partitioning step (O(n² * k)).

Space and Time Complexity

Time Complexity: O(n² * k), where n is the length of the string.
Space Complexity: O(n² + n*k), due to the auxiliary table for palindrome conversion and the DP table.

Solution

The solution involves two main steps:

  1. Precomputation: Compute a cost matrix where cost[i][j] gives the minimum number of changes needed to convert the substring s[i...j] into a palindrome. This is achieved by a two-pointer technique comparing corresponding characters and counting the mismatches.

  2. Dynamic Programming: Define dp[i][p] to be the minimum number of changes required for the substring s[0...i-1] partitioned into p palindromic substrings. Initialize the base case for one partition and derive the recurrence:

    • For each possible partition ending at index i, iterate over previous indices j and update dp[i][p] as: dp[i][p] = min(dp[i][p], dp[j][p-1] + cost[j][i-1]) where cost[j][i-1] is the precomputed cost to convert the substring s[j...i-1] into a palindrome.

The final answer is dp[n][k] where n is the length of s.

Code Solutions

# Python solution for Palindrome Partitioning III

def palindromePartition(s: str, k: int) -> int:
    n = len(s)
    # Precompute cost for converting substring s[i:j+1] into a palindrome
    cost = [[0] * n for _ in range(n)]
    for length in range(2, n+1):  # substring lengths from 2 to n
        for i in range(0, n - length + 1):
            j = i + length - 1
            # If characters at the endpoints are not matching, one change is required plus inner cost
            if s[i] == s[j]:
                cost[i][j] = cost[i+1][j-1] if i+1 <= j-1 else 0
            else:
                cost[i][j] = cost[i+1][j-1] + 1 if i+1 <= j-1 else 1

    # dp[i][p] represents the minimum changes needed for s[0:i] with p partitions
    dp = [[float('inf')] * (k+1) for _ in range(n+1)]
    
    # Base case: for one partition, cost is precomputed for s[0:i-1]
    for i in range(1, n+1):
        dp[i][1] = cost[0][i-1]

    # Fill dp for partitions from 2 to k
    for p in range(2, k+1):
        for i in range(p, n+1):  # i must be at least p to form p non-empty substrings
            for j in range(p-1, i):
                dp[i][p] = min(dp[i][p], dp[j][p-1] + cost[j][i-1])
    
    return dp[n][k]

# Example usage:
#print(palindromePartition("abc", 2))
← Back to All Questions