You are given a string s containing lowercase letters and an integer k. You need to :
s to other lowercase English letters.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.Problem Overview: You are given a string s and an integer k. The goal is to split the string into exactly k non‑empty substrings so that every substring becomes a palindrome after the fewest character changes. Return the minimum number of modifications required.
Approach 1: Dynamic Programming with 2D Arrays (O(n^3) time, O(n^2) space)
This approach builds the solution directly with dynamic programming. Define dp[i][p] as the minimum cost to partition the first i characters into p palindromic substrings. For every split position j, compute the cost of converting substring s[j..i] into a palindrome using a two‑pointer comparison from both ends. The transition becomes dp[i][p] = min(dp[j-1][p-1] + cost(j,i)). Since the palindrome cost is recalculated during transitions, each state may scan the substring, resulting in O(n^3) total time.
This solution is straightforward to implement and mirrors how you reason about the partitions. However, repeated palindrome cost calculations make it slower for larger inputs.
Approach 2: Dynamic Programming with Auxiliary Cost Calculation (O(n^2 * k) time, O(n^2 + n*k) space)
The optimization is to precompute the cost of converting every substring s[i..j] into a palindrome. Build a cost[i][j] table where each entry counts mismatched pairs using a bottom‑up dynamic programming relation. This preprocessing takes O(n^2) time by expanding substrings and comparing characters.
Once the cost table is ready, compute dp[i][p] for partitions. For each ending index i and partition count p, iterate over previous split points j and use the precomputed value cost[j][i]. The transition becomes constant time, reducing overall complexity to O(n^2 * k). This technique is common in dynamic programming problems where substring costs repeat frequently.
Because the algorithm repeatedly examines characters and substrings, the problem combines concepts from string processing and partition-based dynamic programming.
Recommended for interviews: Interviewers typically expect the optimized DP with a precomputed palindrome cost table. Starting with the basic DP shows you understand partition transitions, but recognizing repeated substring computations and introducing a cost matrix demonstrates stronger algorithmic optimization skills.
This approach involves using dynamic programming to compute the minimal number of character changes required to convert certain substrings into palindromes and then partition.
We will use a 2D DP array where dp[i][j] represents the minimal number of changes needed to partition the first i characters of the string into j palindromes.
The function costToMakePalindrome calculates the cost to convert the substring into a palindrome.
The DP table is filled by checking all possible partitions and finding the minimal possible changes required. This requires iterating through all possible partitions at each level.
Time Complexity: O(n^2 * k), where n is the length of the string.
Space Complexity: O(n * k) due to the DP table.
An alternative approach is to precompute the cost of making each substring of the input a palindrome and then use dynamic programming to calculate the minimal number of changes necessary for the entire substring partitioning.
The C solution first calculates the cost of turning every substring into a palindrome, storing it in the cost array. The main DP table is then filled by determining the minimum cost for dividing the string into partitions in k groups.
Time Complexity: O(n^2) for preprocessing cost table + O(n^2 * k) for DP.
Space Complexity: O(n^2 + n * k).
We define f[i][j] to represent the minimum number of changes needed to partition the first i characters of the string s into j palindromic substrings. We assume the index i starts from 1, and the answer is f[n][k].
For f[i][j], we can enumerate the position h of the last character of the (j-1)-th palindromic substring. Then f[i][j] is equal to the minimum value of f[h][j-1] + g[h][i-1], where g[h][i-1] represents the minimum number of changes needed to turn the substring s[h..i-1] into a palindrome (this part can be preprocessed with a time complexity of O(n^2)).
The time complexity is O(n^2 times k), and the space complexity is O(n times (n + k)). Where n is the length of the string s.
| Approach | Complexity |
|---|---|
| Dynamic Programming with 2D Arrays | Time Complexity: O(n^2 * k), where n is the length of the string. |
| Dynamic Programming with Auxiliary Cost Calculation | Time Complexity: O(n^2) for preprocessing cost table + O(n^2 * k) for DP. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with 2D Arrays | O(n^3) | O(n^2) | Good for understanding the partition DP idea without extra preprocessing |
| Dynamic Programming with Auxiliary Cost Calculation | O(n^2 * k) | O(n^2 + n*k) | Best practical solution; avoids recomputing palindrome costs for substrings |
花花酱 LeetCode 1278. Palindrome Partitioning III - 刷题找工作 EP280 • Hua Hua • 3,394 views views
Watch 5 more video solutions →Practice Palindrome Partitioning III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor