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 III

Difficulty: Hard

Problem Description

You are given a string s containing lowercase letters and an integer k. You need to change some characters of s to other lowercase English letters, and then divide s into k non-empty disjoint substrings such that each substring is a palindrome. Return the minimal number of characters that you need to change to divide the string.

Key Insights

  • A palindrome reads the same forwards and backwards.
  • The problem can be approached using dynamic programming to minimize character changes.
  • We can precompute the number of changes needed to make any substring a palindrome.
  • The challenge is to partition the string into exactly k palindromic substrings.

Space and Time Complexity

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

Solution

To solve this problem, we can use a dynamic programming approach. We will create a 2D array dp where dp[i][j] represents the minimum number of changes required to partition the substring s[0..i] into j palindromic substrings.

  1. First, we create a helper function to count the number of changes needed to make a substring a palindrome.
  2. We fill in the dp table using the results from the helper function to compute the minimum changes.
  3. Finally, we return the value in dp[n-1][k], which gives us the minimum changes for the entire string divided into k parts.

Code Solutions

def minChanges(s: str, k: int) -> int:
    n = len(s)
    
    # Precompute changes needed to make substrings palindromic
    changes = [[0] * n for _ in range(n)]
    
    for i in range(n):
        for j in range(i, -1, -1):
            if s[i] != s[j]:
                changes[j][i] = changes[j][i-1] + 1
            if j < i:
                changes[j][i] = changes[j + 1][i - 1] if changes[j + 1][i - 1] >= 0 else 0
    
    # dp[i][j] represents min changes needed to partition s[0..i] into j palindromes
    dp = [[float('inf')] * (k + 1) for _ in range(n)]
    
    for i in range(n):
        dp[i][1] = changes[0][i]  # Only one partition
        
    for j in range(2, k + 1):
        for i in range(n):
            for p in range(i):
                dp[i][j] = min(dp[i][j], dp[p][j - 1] + changes[p + 1][i])
    
    return dp[n - 1][k]
← Back to All Questions