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:
-
The cost of making a substring palindrome - This is the minimum number of character changes required to make any given substring a palindrome.
-
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 firsti
characters ofs
intoj
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 intoj-1
palindromes. We update ourf[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 strings
of lengthn
intok
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
, whereg[i][j]
will hold the cost for converting the substring froms[i]
tos[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 ins
:- 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 settingg[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 substrings[i+1:j-1]
a palindrome, which we have already calculated (g[i + 1][j - 1]
).
-
Initialize a 2D array
f
, wheref[i][j]
will store the minimum number of changes required to divide the firsti
characters ofs
intoj
palindromes. -
Populate the
f
array using the previously computed costs in theg
array:- Iterate over each position
i
in the string and for each possible number of palindromesj
. - If we are looking for only one palindrome (
j == 1
), the cost is straight from theg
array, since the whole substrings[0:i]
needs to be palindromic. - For more than one palindrome (
j > 1
), we consider all possible previous positionsh
where the last palindrome could have started after (f[h][j-1]
is the cost for the firsth
characters intoj-1
palindromes). We then add the cost of makings[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.
- Iterate over each position
-
The minimum number of changes required to divide the entire string
s
intok
palindromes is then found inf[n][k]
, wheren
is the length ofs
.
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 EvaluatorExample 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.
-
Initialize the 2D array
g
to store the cost of converting substrings to palindromes. Here's how to fillg
:- 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 ong[1][1]
, which is 0, plusint(s[0] != s[2])
, which is 0, thusg[0][2]
= 0).
- For a single character substring, the cost is 0 as one letter is always a palindrome (e.g.,
-
Repeat the process by expanding the substring length until
g
contains the cost for all possible substrings. -
Initialize the 2D array
f
.f[i][j]
will keep track of the minimum number of changes required to split the firsti
characters intoj
palindromes. -
Begin populating
f
. Forj=1
, use the values directly fromg
:f[10][1] = g[0][10]
: the cost to changes[0:11]
into one palindrome.
-
For
j>1
, consider where the last palindrome might start and calculate the cost ofj-1
palindromes before that plus the cost of the last palindrome:- For
f[10][3]
, we check each possible positionh
for the last palindrome to start, calculatef[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 changes[7:11]
into a palindrome.- We do this for all possible
h
, andf[10][3]
will be the minimum of all these values.
- For
-
By the end of this process,
f[n][k]
(withn
being the length ofs
) will store the minimum number of changes we need to splits
intok
palindromes.
Now, applying the approach to our example:
g
might look something like this (assuming we computed all necessary costs):
0 1 2 3 4 5 6 7 8 9 10 0 [0,1,0,...] 1 [0,1,...] 2 [0,...] ... 10 [0]
-
Let's say that
f[6][2]
(min changes to make first 7 characters into 2 palindromes) is2
and the cost to changes[7:11] ("dabra")
into a palindrome is2
(g[7][10] = 2
), then one scenario forf[10][3]
would be2 + 2 = 4
. We would compute all other scenarios similarly and take the minimum. -
Eventually,
f[10][3]
gives us the answer for the entire strings
.
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:
-
The first loop calculates the minimum number of changes required to make all substrings palindromic. This is a double loop where
i
ranges fromn-1
to0
andj
ranges fromi+1
ton
. For eachi, j
pair, it does up toO(1)
work ifi + 1 >= j
or it adds the result of a precomputed value ofg[i+1][j-1]
which itself isO(1)
operation. So this loop runs inO(n^2)
time. -
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 from1
ton
,j
ranges from1
tomin(i, k)
, andh
ranges fromj-1
toi
. The innermost loop runs inO(i)
time because it ranges fromj-1
toi
. Sincej
is at mostk
andk
can be as large asn
, in the worst case, the innermost loop isO(n)
. Out of these three loops, the first two contribute toO(nk)
since for thej
loop, although it could be as large asn
, realistically it is bounded byk
.
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
.
-
The space required for the table
g
isO(n^2)
as it is a 2-dimensional square matrix of sizen
. -
The space required for the table
f
isO(n(k+1))
since it hasn
rows andk+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.
Which technique can we use to find the middle of a linked list?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!