Watch 6 video solutions for Palindrome Partitioning III, a hard level problem involving String, Dynamic Programming. This walkthrough by Hua Hua has 3,394 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |