#1278

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Palindrome Partitioning III

Find the minimal character changes to split a string into k palindromes using precise dynamic programming state transitions.

string dynamic programming

Problem Statement

Given a string s of lowercase letters and an integer k, divide s into k non-empty substrings such that each substring is a palindrome and the total number of character changes is minimized. Return the minimum number of changes required to achieve this partitioning.

For example, if s = "abc" and k = 2, you can split into "ab" and "c". Changing 1 character in "ab" to form a palindrome yields the minimal number of changes. Constraints include 1 <= k <= s.length <= 100 and s consists only of lowercase English letters.

Examples

Example 1

Input: s = "abc", k = 2

Output: 1

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

You can split the string into "aa", "bb" and "c", all of them are palindrome.

Example 3

Input: s = "leetcode", k = 8

Output: 0

Example details omitted.

Constraints

1 <= k <= s.length <= 100.
s only contains lowercase English letters.

Solution Approach

Precompute Palindrome Costs

Compute a 2D table where cost[i][j] is the minimal number of character changes to turn substring s[i..j] into a palindrome. Use two pointers expanding from ends to center to count mismatches efficiently.

Dynamic Programming State Definition

Define dp[i][j] as the minimal changes to split the first i characters into j palindromes. Initialize dp[0][0] = 0 and all others to infinity. Iterate over substrings, updating dp[i][j] using previously computed dp values and precomputed costs.

State Transition and Result

For each dp[i][j], iterate k <= i and update dp[i][j] = min(dp[p][j-1] + cost[p][i-1]) for all valid p. After filling the DP table, dp[n][k] gives the minimal number of changes to partition s into k palindromes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2 * k) due to iterating over all substrings for each partition count, and space complexity is O(n^2 + n*k) for storing palindrome costs and DP states.

What Interviewers Usually Probe

Check if candidate precomputes substring palindrome costs efficiently.
Look for correct DP state definition and transition logic.
Verify handling of edge cases where k equals string length or 1.

Common Pitfalls or Variants

Common pitfalls

Forgetting to precompute palindrome costs leading to TLE.
Incorrect DP initialization causing invalid minimal values.
Overlooking edge cases such as single-character substrings or k equal to string length.

Follow-up variants

Minimizing changes to form exactly k palindromic substrings with additional character constraints.
Allowing deletions instead of changes to form k palindromes.
Extending the problem to partition into palindromes with maximum length constraints.

FAQ

What is the best approach for Palindrome Partitioning III?

Use precomputed palindrome costs and a DP table where dp[i][j] stores minimal changes for first i characters into j palindromes.

How do I handle single-character substrings in this problem?

Single-character substrings are already palindromes, so their cost is zero, simplifying the DP transitions.

Why precompute palindrome costs?

Precomputing avoids recalculating changes for the same substring multiple times, reducing overall complexity.

What is the time complexity of this DP solution?

Time complexity is O(n^2 * k) due to iterating over all substrings for each partition count.

Can this approach handle k equal to the string length?

Yes, each character forms its own palindrome, resulting in zero changes, which the DP table correctly captures.

terminal

Solution

Solution 1: Dynamic Programming

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]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        g = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                g[i][j] = int(s[i] != s[j])
                if i + 1 < j:
                    g[i][j] += g[i + 1][j - 1]

        f = [[0] * (k + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, min(i, k) + 1):
                if j == 1:
                    f[i][j] = g[0][i - 1]
                else:
                    f[i][j] = inf
                    for h in range(j - 1, i):
                        f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1])
        return f[n][k]

Continue Practicing

#1255 maximum score words formed by letters #1312 minimum insertion steps to make a string palindrome #1320 minimum distance to type a word using two fingers