Leetcode 1278. Palindrome Partitioning III

Problem Explanation

Given a string 's' containing lowercase letters and an integer 'k', we need to find the minimum number of changes required to convert the string into 'k' palindromes. We have to split the string into 'k' non-empty disjoint substrings such that each substring is a palindrome.

A palindrome is a word, phrase, number, or other sequences of characters that reads the same forward and backward, ignoring spaces, punctuation, and capitalization.

For example, if we have string s = "abc" and k = 2, we can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome. So, the output will be 1.

Approach

The solution to this problem is implemented using dynamic programming.

• The dynamic programming table dp[i][j] is initialised where dp[i][j] represents the minimum number of changes required to convert the string up to the 'i-th' index into 'j' palindromes.

• Another dynamic programming table cost[i][j] is created where cost[i][j] represents the minimum cost to make s[i...j] a palindrome.

• We then fill the table cost[][] using the condition (s[i] != s[j]) + cost[i + 1][j - 1] which checks if both the characters at 'i-th' and 'j-th' index are same or not and adds the value to the cost of transforming the substring excluding the elements at 'i-th' and 'j-th' index into a palindrome.

• Now, we fill the dp[][] table such that for every index we find all possible partitions for the string till that index and give it to the palindromePartition function recursively along with k-1 (since we have partitioned the string once).

• It keeps dividing the string into smaller chunks till k equals to 1 (base condition for the dp function). At this point, it returns the minimum cost to change the substring into a palindrome which makes up the cost for the smaller partition before it.

• Finally, dp[n][k] is returned which consists of the minimum number of changes required to change the string into 'k' palindromes.

Let's implement this approach in Python, Java, Javascript, C++, and C# languages.

Python Solution

1
2python
3class Solution:
4    def palindromePartition(self, s: str, k: int) -> int:
5        n = len(s)
6        # dp table to store minimum changes required up to ith index for j palindromes
7        dp = [[0 if i==0 else float('inf') for j in range(k+1)] for i in range(n+1)]
8        # cost table to store minimum changes to make substring a palindrome
9        cost = [[0]*n for _ in range(n)]
10        for span in range(2, n + 1):
11            for start in range(n - span + 1):
12                end = start + span - 1
13                cost[start][end] = cost[start+1][end-1] + int(s[start] != s[end])
14        for i in range(1, n + 1):
15            if i <= k: 
16                dp[i][i] = 0  
17                continue
18            for j in range(1, min(i, k) + 1):
19                for i1 in range(j-1, i):
20                    dp[i][j] = min(dp[i][j], dp[i1][j-1] + cost[i1][i-1])
21        return dp[n][k]

Java Solution

1
2java
3class Solution {
4    public int palindromePartition(String s, int k) {
5        int n = s.length();
6        int[][] dp = new int[n + 1][k + 1];
7        int[][] cost = new int[n][n];
8        int i, j, l, m;
9        // Initialise dp array
10        for(i = 0; i <= n; i++)
11            for(j = 0; j <= k; j++)
12                dp[i][j] = i == 0 ? 0 : Integer.MAX_VALUE;
13        // Calculate cost to make substrings palindrome
14        for(m = 1; m < n; m++)
15            for(i = 0, j = m; j < n; i++, j++)
16                cost[i][j] = cost[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
17        // Calculate minimum changes required for palindromes
18        for(i = 1; i <= n; i++){
19            for(j = 1; j <= Math.min(i, k); j++){
20                if(j == 1) {
21                    dp[i][j] = cost[0][i - 1];
22                    continue;
23                }
24                for(m = j - 1; m < i; m++)
25                    dp[i][j] = Math.min(dp[m][j - 1] + cost[m][i - 1], dp[i][j]);
26            }
27        }
28        return dp[n][k];
29    }
30}

C++ Solution

1
2c++
3class Solution {
4public:
5    int palindromePartition(string s, int k) {
6        const int n = s.length();
7        // dp array
8        vector<vector<int>> dp(n + 1, vector<int>(k + 1, n));
9        // cost array
10        vector<vector<int>> cost(n, vector<int>(n));
11        // calculate cost
12        for (int d = 1; d < n; ++d)
13            for (int i = 0, j = d; j < n; ++i, ++j)
14                cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1];
15        return palindromePartition(n, k, dp, cost);
16    }
17    
18private:
19    int palindromePartition(int n, int k, vector<vector<int>> &dp, vector<vector<int>> &cost) {
20        if (k == 1)
21            return cost[0][n - 1];
22        int& ans = dp[n][k];
23        if (ans < n)
24            return ans;
25        // try all possible partitions
26        for (int i = k - 1; i < n; ++i)
27            ans = min(ans, palindromePartition(i, k - 1, dp, cost) + cost[i][n - 1]);
28        return ans;
29    }
30};

C# Solution

1
2csharp
3public class Solution {
4    public int PalindromePartition(string s, int k) {
5        int n = s.Length;
6        int[][] dp = new int[n+1][];
7        int[][] cost = new int[n][];
8        for(int i = 0; i <= n; i++)
9            dp[i] = new int[k+1];
10        for(int i = 0; i < n; i++)
11            cost[i] = new int[n];
12        // calculate cost to convert substring into palindrome
13        for(int m = 1; m < n; m++)
14            for(int i = 0, j = m; j < n; i++, j++)
15                cost[i][j] = cost[i+1][j-1] + (s[i] == s[j] ? 0 : 1);
16        // calculate minimum changes required
17        for(int i = 0; i <= n; i++){
18            for(int j = 0; j <= Math.Min(i, k); j++){
19                if(j == 0 || j > i)
20                    dp[i][j] = int.MaxValue;
21                else if(j == 1)
22                    dp[i][j] = cost[0][i-1];
23                else
24                    for(int m = j - 1; m < i; m++)
25                        dp[i][j] = Math.Min(dp[m][j-1] + cost[m][i-1], dp[i][j]);
26            }
27        }
28        return dp[n][k];
29    }
30}

Javascript Solution

1
2javascript
3var palindromePartition = function(s, k) {
4    const n = s.length;
5    const dp = Array(n + 1).fill().map(() => Array(k + 1).fill(n));
6    const cost = Array(n).fill().map(() => Array(n).fill(0));
7    
8    // cost
9    for(let d = 1; d < n; ++d){
10        for(let i = 0, j = d; j < n; ++i, ++j){
11            cost[i][j] = (s[i] !== s[j]) + cost[i + 1][j - 1];
12        }
13    }
14    
15    return helper(n, k, dp, cost);
16};
17
18const helper = function(n, k, dp, cost){
19    if (k === 1) return cost[0][n - 1];
20    if(dp[n][k] < n) return dp[n][k];
21    
22    for(let i = k - 1; i < n; ++i){
23        dp[n][k] = Math.min(dp[n][k], helper(i, k - 1, dp, cost) + cost[i][n - 1]);
24    }
25    
26    return dp[n][k];
27}

In these function, palindromePartition takes in the string s and integer k and calculates the minimum number of character changes needed to convert the string into k palindromes by using a dynamic programming approach.The overall time complexity of these solutions in Python, Java, Javascript, C++, and C# can be estimated as O(n^2 * k). Here, 'n' denotes the length of the input string and 'k' is the number of palindromes. The space complexity of the solutions is O(n^2 + nk), required for the 'cost' and 'dp' tables.

In most of these solutions, helper function is utilised to divide the string into smaller chunks and calculate the minimum number of changes to convert those smaller parts into palindromes. It keeps doing this recursively until 'k' equal to 1 is achieved, which is the base condition for the function, returning the minimum cost to convert the string into 'k' palindromes.

The dynamic programming approach with the combination of helper function helps to solve this problem with minimized time and space complexity. It works by remembering smaller sub-problems to get to the bigger problems in a recursive way, eventually giving the minimum number of changes needed to have the string form 'k' palindromes.

Therefore, with the blend of dynamic programming and understanding of palindromes, this problem can be solved efficiently in different programming languages.