{x}
blog image

Palindrome Partitioning III

You are given a string s containing lowercase letters and an integer k. You need to :

  • First, change some characters of s to other lowercase English letters.
  • 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.

 

Example 1:

Input: s = "abc", k = 2
Output: 1
Explanation: You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.

Example 2:

Input: s = "aabbc", k = 3
Output: 0
Explanation: You can split the string into "aa", "bb" and "c", all of them are palindrome.

Example 3:

Input: s = "leetcode", k = 8
Output: 0

 

Constraints:

  • 1 <= k <= s.length <= 100.
  • s only contains lowercase English letters.

Solution Explanation for Palindrome Partitioning III

This problem asks for the minimum number of character changes needed to partition a string into k palindromic substrings. The solution uses dynamic programming to efficiently find this minimum.

Core Idea:

The solution leverages a two-dimensional dynamic programming approach. The states are defined as:

  • g[i][j] : The minimum number of character changes needed to make the substring s[i...j] a palindrome. This is pre-calculated.
  • f[i][j] : The minimum number of character changes needed to partition the substring s[0...i] into j palindromic substrings. This is what we want to compute.

Algorithm:

  1. Precompute g[i][j]: This array represents the cost of making each substring a palindrome. We iterate through all possible substrings. If the substring's endpoints characters are different, we increment a counter. Then, recursively add the cost of the inner substring (excluding endpoints) to get the total cost for making the substring a palindrome.

  2. Dynamic Programming (f[i][j]): This is the core DP step. We build f[i][j] bottom-up:

    • Base Case: f[i][1] (partitioning into one substring) is simply the cost of making s[0...i] a palindrome (g[0][i]).

    • Recursive Step: For f[i][j] (where j > 1), we consider all possible positions h to place the (j-1)th partition boundary. We minimize over all such positions, using:

      f[i][j] = min(f[i][j], f[h][j-1] + g[h+1][i])

      This means we partition s[0...i] by putting the (j-1)th boundary at position h. The cost is the cost of partitioning the left substring s[0...h] into j-1 substrings (f[h][j-1]), plus the cost of making the right substring s[h+1...i] a palindrome (g[h+1][i]).

  3. Result: f[n][k] (where n is the string length) will contain the minimum number of character changes to partition the entire string into k palindromic substrings.

Time Complexity: O(n³k), where n is the length of the string and k is the number of partitions. The precomputation of g takes O(n²) time. The DP step iterates through O(n) positions for each f[i][j], resulting in a total time complexity of O(n²k).

Space Complexity: O(n² + nk). This is dominated by the g and f arrays.

Code Explanation (Python):

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        g = [[0] * n for _ in range(n)] # precompute palindrome costs
        # ... (precompute g[i][j] as described above) ...
 
        f = [[float('inf')] * (k + 1) for _ in range(n + 1)] # initialize DP array
        for i in range(1, n + 1):
            f[i][1] = g[0][i - 1] # base case: one partition
 
        for i in range(1, n + 1):
            for j in range(2, min(i, k) + 1): # iterate through partitions
                for h in range(j - 1, i): # iterate through partition boundaries
                    f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1])
 
        return f[n][k]

The other languages (Java, C++, Go) implement the same algorithm with minor syntactic differences. The core logic of precomputing g and then performing the dynamic programming to find f remains the same across all implementations.