1278. Palindrome Partitioning III


Problem Description

The given problem presents a scenario where we have a string s comprising lowercase English letters and an integer k. Our objective is to carry out two tasks. Firstly, we are to modify some of the characters in s into other lowercase English letters. Secondly, we must divide the modified string into k non-empty, disjoint substrings with the condition that each of these substrings must be a palindrome.

A palindrome is a sequence of characters which reads the same backward as forward (for example, "radar" or "level"). The goal is to achieve this division by making the minimal number of character changes in the original string s.

Intuition

To solve this problem, we need to consider two main aspects:

  1. The cost of making a substring palindrome - This is the minimum number of character changes required to make any given substring a palindrome.

  2. The optimal way to partition the string into k palindromes - Once we understand how to compute the cost for single substrings, we need to figure out an optimal way to partition the string into k segments such that the total cost (the sum of the costs of making all substrings palindromic) is minimized.

Here is the thought process to arrive at the solution approach:

  • First, we need to calculate the cost of converting every possible substring into a palindrome. We do this by using dynamic programming to precompute and store the costs in a 2D array.

  • Next, we use another 2D dynamic programming array, where f[i][j] represents the minimum number of changes needed to split the first i characters of s into j palindromes.

  • The dynamic step progresses by considering all possible splits of the string where the rightmost palindrome ends just before the i-th character and the rest of the string is split into j-1 palindromes. We update our f[i][j] value by finding the minimum among all these possibilities.

  • The final solution, f[n][k], would be the minimal number of changes to divide the complete string s of length n into k palindromic substrings.

By carefully computing these costs and properly combining them while maintaining the imposed conditions, we can incrementally construct the solution, allowing us to find the minimum total cost requested.

In the solution code given, g[i][j] is used to store the cost of converting the substring s[i:j+1] into a palindrome. The array f[i][j] keeps track of the minimum number of changes for the first i characters of s into j palindromes. The nested loops are used to calculate these values, using previously computed ones, which underline the dynamic programming approach.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution utilizes Dynamic Programming (DP), a method for solving complex problems by breaking them down into simpler subproblems. The approach uses two DP arrays, g and f, to store intermediate results and build up the solution progressively. Here is a breakdown of how the solution approach is implemented:

  • Initialize a 2D array g, where g[i][j] will hold the cost for converting the substring from s[i] to s[j] into a palindrome. The cost is the number of characters that need to be changed.

  • Fill the g array with the necessary costs. This involves iterating over all possible substrings in s:

    • Starting from the end of the string and moving backwards ensures that we calculate the costs for smaller substrings first. This is essential since the cost of a larger substring might depend on the cost of its smaller substrings.
    • For each pair of indices (i, j), we start by setting g[i][j] to be one if the characters at these indices are different (int(s[i] != s[j])), signifying a single necessary change to help form a palindrome.
    • If we have a substring longer than two characters (i + 1 < j), we add the cost of making the inner substring s[i+1:j-1] a palindrome, which we have already calculated (g[i + 1][j - 1]).
  • Initialize a 2D array f, where f[i][j] will store the minimum number of changes required to divide the first i characters of s into j palindromes.

  • Populate the f array using the previously computed costs in the g array:

    • Iterate over each position i in the string and for each possible number of palindromes j.
    • If we are looking for only one palindrome (j == 1), the cost is straight from the g array, since the whole substring s[0:i] needs to be palindromic.
    • For more than one palindrome (j > 1), we consider all possible previous positions h where the last palindrome could have started after (f[h][j-1] is the cost for the first h characters into j-1 palindromes). We then add the cost of making s[h:i] a palindrome (g[h][i - 1]).
    • We take the minimum of all these possible previous positions h to ensure we have the least number of changes.
  • The minimum number of changes required to divide the entire string s into k palindromes is then found in f[n][k], where n is the length of s.

The variables i, j, and h represent indices in the string s and the loops over these indices address the subproblems in a bottom-up manner, allowing the solution to be assembled incrementally. The inf value serves as an initial high cost to ensure that any actual cost calculated will be lower, enabling the min function to work correctly.

Through this approach, all possible ways to form k palindromes out of the string s by making the fewest changes are evaluated efficiently. The nested loops ensure that every necessary substring and partition count scenario is considered, while previous calculations are reused, following the typical dynamic programming pattern of solving overlapping subproblems and optimizing the decision at each step.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example. Suppose we have the string s = "abracadabra" and we want to split it into k = 3 palindromic substrings, making the minimum number of character changes.

  1. Initialize the 2D array g to store the cost of converting substrings to palindromes. Here's how to fill g:

    • For a single character substring, the cost is 0 as one letter is always a palindrome (e.g., g[0][0], g[1][1], ..., g[10][10] should all be 0).
    • For two character substrings, if the characters are the same, the cost is 0. If different, the cost is 1 (e.g., g[0][1] is 1 as 'a' != 'b', g[2][3] is 1 as 'r' != 'a').
    • For three or more character substrings, the cost is dependent on the first and last characters and the cost of the inner substring (e.g., g[0][2] would depend on g[1][1], which is 0, plus int(s[0] != s[2]), which is 0, thus g[0][2] = 0).
  2. Repeat the process by expanding the substring length until g contains the cost for all possible substrings.

  3. Initialize the 2D array f. f[i][j] will keep track of the minimum number of changes required to split the first i characters into j palindromes.

  4. Begin populating f. For j=1, use the values directly from g:

    • f[10][1] = g[0][10]: the cost to change s[0:11] into one palindrome.
  5. For j>1, consider where the last palindrome might start and calculate the cost of j-1 palindromes before that plus the cost of the last palindrome:

    • For f[10][3], we check each possible position h for the last palindrome to start, calculate f[h][2] + g[h+1][10] and find the minimum. For instance:
      • f[6][2] + g[7][10]: The cost to change the first 7 characters into 2 palindromes and the cost to change s[7:11] into a palindrome.
      • We do this for all possible h, and f[10][3] will be the minimum of all these values.
  6. By the end of this process, f[n][k] (with n being the length of s) will store the minimum number of changes we need to split s into k palindromes.

Now, applying the approach to our example:

  • g might look something like this (assuming we computed all necessary costs):
1   0 1 2 3 4 5 6 7 8  9 10
20 [0,1,0,...]
31    [0,1,...]
42       [0,...]
5...
610          [0] 
  • Let's say that f[6][2] (min changes to make first 7 characters into 2 palindromes) is 2 and the cost to change s[7:11] ("dabra") into a palindrome is 2 (g[7][10] = 2), then one scenario for f[10][3] would be 2 + 2 = 4. We would compute all other scenarios similarly and take the minimum.

  • Eventually, f[10][3] gives us the answer for the entire string s.

This example walkthrough demonstrates how dynamic programming allows us to efficiently compute and combine the costs of smaller problems to solve the larger problem at hand.

Solution Implementation

1class Solution:
2    def palindromePartition(self, s: str, k: int) -> int:
3        # Calculate the length of the string
4        length = len(s)
5        # Initialize a table to store the minimum number of changes required
6        # to make a substring a palindrome
7        changes = [[0] * length for _ in range(length)]
8      
9        # Calculate the changes required for all substrings
10        for start in range(length - 1, -1, -1):
11            for end in range(start + 1, length):
12                # A single character change if the start and end are different
13                changes[start][end] = int(s[start] != s[end])
14                # If the substring is longer than 2 characters,
15                # add the changes required for the inner substring
16                if start + 1 < end:
17                    changes[start][end] += changes[start + 1][end - 1]
18
19        # Initialize a table to store the minimum number of changes required
20        # for the first i characters of s, split into j partitions
21        dp = [[float('inf')] * (k + 1) for _ in range(length + 1)]
22      
23        # Fill the table with dynamic programming approach
24        for i in range(1, length + 1):
25            for j in range(1, min(i, k) + 1):
26                # If there's only one partition, store the changes required
27                # to make the entire substring a palindrome
28                if j == 1:
29                    dp[i][j] = changes[0][i - 1]
30                else:
31                    # For more than one partition, find the minimum changes required
32                    for h in range(j - 1, i):
33                        # Update the dp table with the minimum of the previous value
34                        # and the sum of changes required for the partition before h
35                        # and the changes required for the substring from h to i - 1
36                        dp[i][j] = min(dp[i][j], dp[h][j - 1] + changes[h][i - 1])
37                      
38        # Return the minimum changes required for the entire string with k partitions
39        return dp[length][k]
40
1class Solution {
2    public int palindromePartition(String s, int k) {
3        // 'n' represents the length of string 's'.
4        int n = s.length();
5
6        // 'changeCount' table stores the minimum changes required to make a substring a palindrome.
7        int[][] changeCount = new int[n][n];
8
9        // Build the 'changeCount' table in bottom-up fashion where each entry changeCount[i][j]
10        // represents the minimum changes required to make the substring from index 'i' to 'j' a palindrome.
11        for (int i = n - 1; i >= 0; --i) {
12            for (int j = i; j < n; ++j) {
13                // If characters are different, one change is required.
14                // If they are the same, no change is required.
15                changeCount[i][j] = s.charAt(i) != s.charAt(j) ? 1 : 0;
16
17                // If the substring is longer than 2 characters, add the change count of the inner substring.
18                if (i + 1 < j) {
19                    changeCount[i][j] += changeCount[i + 1][j - 1];
20                }
21            }
22        }
23
24        // 'dp' table where dp[i][j] stores the minimum changes required for making 'j' partitions on the first 'i' characters.
25        int[][] dp = new int[n + 1][k + 1];
26
27        // Iterate through each substring length from 1 to 'n'.
28        for (int i = 1; i <= n; ++i) {
29            // Iterate through each possible partition count from 1 to minimum of 'i' or 'k' partitions.
30            for (int j = 1; j <= Math.min(i, k); ++j) {
31                // If there is only one partition, the cost is the cost to make the entire substring a palindrome.
32                if (j == 1) {
33                    dp[i][j] = changeCount[0][i - 1];
34                } else {
35                    // Initialize the value with a large number that will be overwritten by the minimum cost found.
36                    dp[i][j] = 10000;
37
38                    // Check for all possible partitions and calculate the minimum cost to make 'j' partitions.
39                    for (int h = j - 1; h < i; ++h) {
40                        dp[i][j] = Math.min(dp[i][j], dp[h][j - 1] + changeCount[h][i - 1]);
41                    }
42                }
43            }
44        }
45
46        // Return the minimum number of changes needed for 'k' partitions in the entire string.
47        return dp[n][k];
48    }
49}
50
1#include <vector>
2#include <string>
3#include <algorithm>
4
5using std::string;
6using std::vector;
7using std::min;
8
9class Solution {
10public:
11    // Function to partition the string into k palindromic substrings.
12    // It minimizes the number of characters changed to achieve this.
13    int palindromePartition(string s, int k) {
14        int n = s.size();
15        // Create a 2D vector to store the number of characters that need to be
16        // changed to make substrings palindromic.
17        vector<vector<int>> changesNeeded(n, vector<int>(n));
18      
19        // Calculate the changes needed for all possible substrings.
20        for (int start = n - 1; start >= 0; --start) {
21            for (int end = start; end < n; ++end) {
22                // If the outer characters are the same, no change is needed,
23                // else one change is needed.
24                changesNeeded[start][end] = s[start] != s[end] ? 1 : 0;
25                if (start + 1 < end) {
26                    // If we have more than two characters, consider the internal
27                    // substring as well.
28                    changesNeeded[start][end] += changesNeeded[start + 1][end - 1];
29                }
30            }
31        }
32      
33        // Create a 2D vector to store the minimum changes needed to partition substrings
34        // up to i into j palindromes.
35        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
36      
37        // Start to populate the dp table from the start of the string.
38        for (int i = 1; i <= n; ++i) {
39            for (int j = 1; j <= min(i, k); ++j) {
40                if (j == 1) {
41                    // When we have only one partition, all the changes are required for the whole substring.
42                    dp[i][j] = changesNeeded[0][i - 1];
43                } else {
44                    // Initialize with a maximum number or an arbitrarily large number.
45                    dp[i][j] = 10000; 
46                    for (int h = j - 1; h < i; ++h) {
47                        // Check partitioning the string at each point h and find the minimum changes required.
48                        dp[i][j] = min(dp[i][j], dp[h][j - 1] + changesNeeded[h][i - 1]);
49                    }
50                }
51            }
52        }
53        // The last element of the dp table will be the result.
54        return dp[n][k];
55    }
56};
57
1function palindromePartition(s: string, k: number): number {
2    const n: number = s.length;
3    // Initialize a 2D array to store the number of changes needed
4    // for each substrings to become palindromic.
5    let changesNeeded = Array.from(Array(n), () => new Array(n).fill(0));
6  
7    // Pre-calculate the number of changes needed for all substrings.
8    for (let start = n - 1; start >= 0; --start) {
9        for (let end = start; end < n; ++end) {
10            // For a substring with identical start and end characters, no changes are needed,
11            // otherwise, one change is needed.
12            changesNeeded[start][end] = s[start] != s[end] ? 1 : 0;
13            if (start + 1 < end) {
14                // Add the number of changes needed for the internal part of the substring.
15                changesNeeded[start][end] += changesNeeded[start + 1][end - 1];
16            }
17        }
18    }
19  
20    // Use dynamic programming to calculate the minimum changes needed
21    // to partition the string into k palindromic substrings.
22    let dp = Array.from(Array(n + 1), () => new Array(k + 1).fill(0));
23  
24    // Fill out the DP table.
25    for (let i = 1; i <= n; ++i) {
26        for (let j = 1; j <= Math.min(i, k); ++j) {
27            if (j === 1) {
28                // If there's only one partition, it's simply the total changes for the whole substring.
29                dp[i][j] = changesNeeded[0][i - 1];
30            } else {
31                // Initialize with a high number that acts as infinity.
32                dp[i][j] = Infinity;
33                for (let h = j - 1; h < i; ++h) {
34                    // Update the DP value for dp[i][j] by finding the minimum changes
35                    // across different partitioning options.
36                    dp[i][j] = Math.min(dp[i][j], dp[h][j - 1] + changesNeeded[h][i - 1]);
37                }
38            }
39        }
40    }
41    // The answer is the minimum changes needed to partition the entire string into k palindromes.
42    return dp[n][k];
43}
44
45// The methods and variables can now be directly used in TypeScript without the need for a class.
46

Time and Space Complexity

The given code snippet is designed to find the minimum number of characters that need to be changed to create k palindromic substrings from the given string s.

Time Complexity

The time complexity of the algorithm can be analyzed as follows:

  1. The first loop calculates the minimum number of changes required to make all substrings palindromic. This is a double loop where i ranges from n-1 to 0 and j ranges from i+1 to n. For each i, j pair, it does up to O(1) work if i + 1 >= j or it adds the result of a precomputed value of g[i+1][j-1] which itself is O(1) operation. So this loop runs in O(n^2) time.

  2. The second loop computes the minimum number of changes to make exactly k palindromic substrings by building up a solution using dynamic programming. This involves triple nested loops: i ranges from 1 to n, j ranges from 1 to min(i, k), and h ranges from j-1 to i. The innermost loop runs in O(i) time because it ranges from j-1 to i. Since j is at most k and k can be as large as n, in the worst case, the innermost loop is O(n). Out of these three loops, the first two contribute to O(nk) since for the j loop, although it could be as large as n, realistically it is bounded by k.

Thus, the overall time complexity of the second loop is O(n^2k) since for each of the O(nk) outer loop iterations, the innermost loop might run in O(n) time.

Combining both parts, the time complexity of the algorithm can be described as O(n^2 + n^2k), which simplifies to O(n^2k) due to the dominating term when k is not constant.

The final expression to represent the time complexity is:

O(n^2k)

Space Complexity

The space complexity is determined by the space used by the dynamic programming table f and the table g.

  1. The space required for the table g is O(n^2) as it is a 2-dimensional square matrix of size n.

  2. The space required for the table f is O(n(k+1)) since it has n rows and k+1 columns.

Therefore, the total space complexity is the sum of the two space requirements which is:

O(n^2) + O(nk)

However, the space complexity can be bounded by the larger term, which is O(n^2) when k is not constant.

The final expression to represent the space complexity is:

O(n^2)

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?


Recommended Readings