Palindrome Partitioning III: Minimum Changes to Split into K Palindromes

You are given a string s and an integer k. Split s into exactly k non-empty substrings. You can change characters in s before or after splitting. The goal is to minimize the total number of character changes needed so that every substring in the partition is a palindrome.

This is LeetCode 1278: Palindrome Partitioning III. It combines two classic ideas: computing the cost to turn any substring into a palindrome, and using partition DP to find the optimal way to split the string into k groups. If you have worked through Palindrome Partitioning II, you will recognize the partition DP structure. The twist here is that instead of requiring zero-cost palindromes and minimizing the number of cuts, you allow character changes and fix the number of partitions at k.

Why this problem is tricky

The challenge is that you need to consider two things at once: where to place the partition boundaries, and how many changes each resulting substring needs. A greedy approach does not work because a partition that looks cheap locally might force expensive changes in the remaining substrings. You need to explore all possible split points, which means dynamic programming.

The key insight is to separate the problem into two layers. First, precompute a cost table that tells you, for every possible substring s[i..j], how many character changes are needed to make it a palindrome. Then use that table inside a partition DP that finds the optimal way to divide the string into k groups.

Layer 1: The palindrome cost table

For any substring s[i..j], you can compute the number of changes needed using two pointers. Start one pointer at i and one at j. If the characters match, move both inward. If they do not match, that is one required change, and you still move both inward. The total number of mismatches is the cost.

def palindrome_cost(s):
    n = len(s)
    cost = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            cost[i][j] = cost[i + 1][j - 1] + (0 if s[i] == s[j] else 1)
    return cost

This fills the table bottom-up by substring length. For length 1, cost is 0 (already on the diagonal). For length 2, cost is 0 if the two characters match and 1 otherwise. Each longer substring builds on the answer for the substring with both endpoints removed.

Time: O(n^2) to fill the table.

Layer 2: Partition DP

Define dp[i][j] as the minimum number of changes to partition s[0..i] into exactly j palindromes.

Base case: dp[i][1] = cost[0][i] for all i. Making the entire prefix s[0..i] into one palindrome costs exactly cost[0][i].

Transition: For j >= 2, try every possible split point p where the last partition starts at p + 1:

dp[i][j] = min(dp[p][j-1] + cost[p+1][i]) for all valid p

This says: take the best way to split s[0..p] into j-1 palindromes, then pay the cost to make s[p+1..i] into one more palindrome.

The answer is dp[n-1][k].

def palindromePartition(s, k):
    n = len(s)
    cost = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            cost[i][j] = cost[i + 1][j - 1] + (0 if s[i] == s[j] else 1)

    dp = [[float('inf')] * (k + 1) for _ in range(n)]
    for i in range(n):
        dp[i][1] = cost[0][i]
        for j in range(2, min(i + 2, k + 1)):
            for p in range(j - 2, i):
                dp[i][j] = min(dp[i][j], dp[p][j - 1] + cost[p + 1][i])

    return dp[n - 1][k]

Walking through the example

Take s = "aabbc" and k = 3. First, compute the cost table. Some key entries: cost[0][0] = 0 (single "a"), cost[0][1] = 0 ("aa" is already a palindrome), cost[0][2] = 1 ("aab" needs one change), cost[2][3] = 0 ("bb" is a palindrome), cost[4][4] = 0 (single "c").

For the base case, dp[i][1] is the cost to make the whole prefix a palindrome: dp[0][1] = 0, dp[1][1] = 0, dp[2][1] = 1, dp[3][1] = 1, dp[4][1] = 2.

When filling dp[4][3], you try split points p = 1, 2, 3:

• p = 1: dp[1][2] + cost[2][4]. dp[1][2] = dp[0][1] + cost[1][1] = 0 + 0 = 0. cost[2][4] = 1. Total = 1.
• p = 2: dp[2][2] + cost[3][4]. dp[2][2] = min(dp[0][1] + cost[1][2], dp[1][1] + cost[2][2]) = min(0 + 1, 0 + 0) = 0. cost[3][4] = 1. Total = 1.
• p = 3: dp[3][2] + cost[4][4]. dp[3][2] = min(dp[0][1] + cost[1][3], dp[1][1] + cost[2][3], dp[2][1] + cost[3][3]) = min(0 + 1, 0 + 0, 1 + 0) = 0. cost[4][4] = 0. Total = 0.

The minimum is 0, achieved by the partition "aa" | "bb" | "c". All three parts are already palindromes, so zero changes are needed.

Complexity analysis

Where n = length of string, k = number of partitions.

The cost table takes O(n^2) time and space. The DP table has O(n * k) entries, and each entry considers O(n) split points, giving O(n^2 * k) total. In practice, since k is at most n, the dominant cost is O(n^3) in the worst case, but typically k is much smaller than n.

The building blocks

This problem is built on two patterns working together:

Palindrome cost precomputation. The cost table uses a two-pointer idea wrapped inside interval DP. You compute costs for all substrings of length 1, then length 2, then length 3, and so on. Each answer builds on the answer for the inner substring with the two endpoints removed.

• State: cost[i][j] = number of character changes to make s[i..j] a palindrome
• Transition: cost[i][j] = cost[i+1][j-1] + (0 if s[i] == s[j] else 1)
• Base case: cost[i][i] = 0, and for i > j, cost[i][j] = 0

Partition DP. This is the same pattern used in Palindrome Partitioning II, where you split a string into groups and optimize some cost over the grouping.

• State: dp[i][j] = min changes to partition s[0..i] into j palindromes
• Transition: dp[i][j] = min over p of dp[p][j-1] + cost[p+1][i]
• Base case: dp[i][1] = cost[0][i]

The combination of a precomputed cost table with a partition DP is a recurring pattern. You will see the same structure in problems like minimum cost to merge stones, burst balloons, and other interval-based optimization problems.

Edge cases to watch for

• k equals the string length: Every character becomes its own partition. Single characters are always palindromes, so the answer is 0.
• k = 1: The entire string must be one palindrome. The answer is cost[0][n-1], the number of changes to make the whole string a palindrome.
• String is already all palindromes: If the string can be split into k parts that are all palindromes with no changes, the answer is 0. For example, s = "aabbcc" with k = 3 gives partitions "aa", "bb", "cc" with zero cost.
• All characters are the same: The string is already a palindrome regardless of how you split it. Answer is always 0 for any k.
• k = n - 1: You split into n - 1 parts. One part has 2 characters, the rest are single characters. The cost is 0 if any adjacent pair matches, and 1 otherwise (just pick the adjacent pair with the highest mismatch cost, but actually you want the minimum, so pick the best pair).

From understanding to recall

You now understand the two-layer approach: precompute palindrome costs, then run partition DP on top. But knowing the structure and reproducing it under time pressure are different skills. In an interview, you need to remember to separate the cost precomputation from the partition DP, set up the base cases correctly for both layers, and handle the loop bounds without off-by-one errors.

The partition DP pattern shows up repeatedly in problems where you split a sequence into groups and optimize a cost. Each time, the ingredients are the same: a precomputed cost function, a DP table indexed by position and number of groups, and a transition that tries all split points. The details change, but the skeleton stays the same.

The palindrome-cost plus partition-DP combination is one of roughly 60 reusable building blocks in the CodeBricks system. Spaced repetition drilling locks in both the cost table construction and the partition transition, so you can write them from memory when it matters. Once this pattern clicks, problems like burst balloons and minimum difficulty of a job schedule become much more approachable.

Related posts

• Palindrome Partitioning - Find all ways to partition a string into palindromes using backtracking. The exploration version of this problem family.
• Palindrome Partitioning II - Minimize the number of cuts so every piece is a palindrome. Same partition DP structure, different optimization target.
• Edit Distance - Another classic DP problem that counts the minimum number of character-level changes. Similar "cost of transformation" thinking.