LeetCode Problem 1278

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

LeetCode 1278 - Palindrome Partitioning III

Problem Understanding

The problem gives us a string s and an integer k. We are allowed to modify characters in the string, and our goal is to partition the string into exactly k non-empty substrings such that every substring becomes a palindrome after the modifications.

A palindrome is a string that reads the same forward and backward. For example, "aba" and "aa" are palindromes, while "abc" is not.

The important detail is that we are not required to preserve the original characters. We may change any character to any lowercase English letter. The objective is to minimize the total number of character changes across all substrings.

For example, if s = "abc" and k = 2, we can split the string into "ab" and "c". The substring "ab" is not a palindrome, but changing either 'a' to 'b' or 'b' to 'a' makes it one. That requires exactly one modification, so the answer is 1.

The constraints are small enough to strongly suggest a dynamic programming solution:

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

Since the maximum string length is only 100, algorithms with cubic complexity are acceptable. Exponential brute force solutions, however, would still be far too slow.

Several edge cases are important:

• When k == s.length, every character can form its own substring, so the answer is always 0.
• When k == 1, the entire string must become one palindrome.
• Some substrings may already be palindromes and require no changes.
• The partition positions significantly affect the total cost, so greedy strategies can fail.

Approaches

Brute Force Approach

A brute force solution would try every possible way to divide the string into k substrings. For each partitioning, we would compute how many character modifications are needed to make every substring a palindrome.

To compute the palindrome cost of a substring, we compare characters from both ends toward the center. Every mismatched pair contributes one required modification.

The main issue is the number of possible partitions. Choosing k - 1 split positions among n - 1 possible locations leads to a combinatorial explosion. Even though checking each partition is relatively cheap, the total number of possibilities becomes impractical.

This approach is correct because it exhaustively evaluates all valid partitions, but it is too slow for n = 100.

Optimal Dynamic Programming Approach

The key observation is that many substring palindrome costs are reused repeatedly across different partitions.

We can separate the problem into two smaller subproblems:

1. Precompute the cost to convert every substring into a palindrome.
2. Use dynamic programming to find the minimum partition cost.

For the first step, define:

• cost[i][j] = minimum changes needed to make s[i:j+1] a palindrome.

This can be computed efficiently using interval DP.

For the second step, define:

• dp[i][p] = minimum cost to partition the substring starting at index i into exactly p palindromic parts.

We try every possible ending position for the first partition, then recursively solve the remaining suffix.

Because overlapping subproblems are heavily reused, dynamic programming dramatically reduces the complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(k)	Tries every partition configuration
Optimal Dynamic Programming	O(n³ + kn²)	O(n² + kn)	Precomputes palindrome costs and uses DP

Algorithm Walkthrough

Step 1: Precompute palindrome conversion costs

Create a 2D array cost where:

• cost[i][j] represents the minimum changes needed to convert substring s[i:j+1] into a palindrome.

To compute this:

1. If i >= j, the substring has length 0 or 1, so the cost is 0.
2. Otherwise:

• Compare s[i] and s[j]
• If they differ, one modification is needed
• Add the cost of the inner substring

The recurrence becomes:

$cost[i][j] = cost[i+1][j-1] + [s_i \neq s_j]$

We process substrings by increasing length so smaller intervals are already computed.

Step 2: Define the DP state

Create a DP table:

• dp[i][p] = minimum cost to partition substring s[i:] into exactly p palindromic substrings.

The final answer will be:

$dp[0][k]$

Step 3: Transition between states

For every state (i, p):

1. Try every possible endpoint j for the first partition.
2. The first substring is s[i:j+1].
3. Its palindrome conversion cost is cost[i][j].
4. The remaining suffix begins at j + 1 and must be partitioned into p - 1 parts.

Transition:

$dp[i][p] = \min_{j \ge i}(cost[i][j] + dp[j+1][p-1])$

Step 4: Base cases

If only one partition remains:

• dp[i][1] = cost[i][n-1]

This means the entire remaining suffix must become one palindrome.

Step 5: Return the answer

The answer is dp[0][k].

Why it works

The algorithm works because every valid partition can be decomposed into:

1. A first palindromic substring.
2. An optimal partitioning of the remaining suffix.

The DP recurrence checks all possible first cuts and chooses the minimum total cost. Since every subproblem is solved optimally and reused consistently, the final result is globally optimal.

Python Solution

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)

        # cost[i][j] = minimum changes needed
        # to make s[i:j+1] a palindrome
        cost = [[0] * n for _ in range(n)]

        # Build costs by substring length
        for length in range(2, n + 1):
            for left in range(n - length + 1):
                right = left + length - 1

                if left + 1 <= right - 1:
                    cost[left][right] = cost[left + 1][right - 1]

                if s[left] != s[right]:
                    cost[left][right] += 1

        INF = float('inf')

        # dp[i][p] = minimum cost to partition
        # s[i:] into p palindromic substrings
        dp = [[INF] * (k + 1) for _ in range(n + 1)]

        # Base case
        dp[n][0] = 0

        for i in range(n - 1, -1, -1):
            dp[i][1] = cost[i][n - 1]

        # Fill DP table
        for parts in range(2, k + 1):
            for start in range(n):
                # Ensure enough characters remain
                for end in range(start, n - parts + 1):
                    dp[start][parts] = min(
                        dp[start][parts],
                        cost[start][end] + dp[end + 1][parts - 1]
                    )

        return dp[0][k]

The implementation starts by precomputing palindrome conversion costs for all substrings. This avoids recalculating mismatch counts repeatedly during partitioning.

The nested loops over substring length ensure that smaller intervals are processed before larger ones. This is necessary because cost[left][right] depends on cost[left + 1][right - 1].

After preprocessing, the algorithm initializes the dynamic programming table. Each entry represents the minimum cost for partitioning a suffix into a specific number of palindromic parts.

The transition iterates over every possible ending index for the first partition. For each candidate split, the algorithm combines:

1. The cost of converting the current substring into a palindrome.
2. The optimal cost for partitioning the remaining suffix.

Finally, dp[0][k] contains the minimum total number of modifications.

Go Solution

func palindromePartition(s string, k int) int {
	n := len(s)

	// cost[i][j] = minimum changes needed
	// to make s[i:j+1] a palindrome
	cost := make([][]int, n)
	for i := range cost {
		cost[i] = make([]int, n)
	}

	// Build palindrome costs
	for length := 2; length <= n; length++ {
		for left := 0; left+length-1 < n; left++ {
			right := left + length - 1

			if left+1 <= right-1 {
				cost[left][right] = cost[left+1][right-1]
			}

			if s[left] != s[right] {
				cost[left][right]++
			}
		}
	}

	const INF = int(1e9)

	// dp[i][p] = minimum cost to partition
	// s[i:] into p palindromic substrings
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, k+1)

		for j := range dp[i] {
			dp[i][j] = INF
		}
	}

	dp[n][0] = 0

	for i := n - 1; i >= 0; i-- {
		dp[i][1] = cost[i][n-1]
	}

	for parts := 2; parts <= k; parts++ {
		for start := 0; start < n; start++ {
			for end := start; end <= n-parts; end++ {
				candidate := cost[start][end] + dp[end+1][parts-1]

				if candidate < dp[start][parts] {
					dp[start][parts] = candidate
				}
			}
		}
	}

	return dp[0][k]
}

The Go implementation follows the same logic as the Python version, but uses slices instead of lists.

Since Go does not provide an infinity constant for integers, a large sentinel value such as 1e9 is used.

The DP arrays are explicitly initialized because Go does not support Python-style list comprehensions. Otherwise, the algorithm structure and recurrence relations remain identical.

Worked Examples

Example 1

Input:

s = "abc"
k = 2

Step 1: Compute palindrome costs

Substring	Cost
"a"	0
"b"	0
"c"	0
"ab"	1
"bc"	1
"abc"	1

For "abc":

• Compare 'a' and 'c'
• They differ, so one change is needed

Step 2: Initialize DP

Base case:

State	Value
dp[2][1]	0
dp[1][1]	1
dp[0][1]	1

Step 3: Compute dp[0][2]

Try all first partitions:

First Partition	Cost	Remaining	Remaining Cost	Total
"a"	0	"bc"	1	1
"ab"	1	"c"	0	1

Minimum = 1

Answer:

1

Example 2

Input:

s = "aabbc"
k = 3

Possible partition:

"aa" | "bb" | "c"

Palindrome costs:

Substring	Cost
"aa"	0
"bb"	0
"c"	0

Total cost:

0

The DP eventually discovers this optimal partition.

Example 3

Input:

s = "leetcode"
k = 8

Each character becomes its own palindrome:

"l" | "e" | "e" | "t" | "c" | "o" | "d" | "e"

Every single-character substring is already a palindrome.

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n³ + kn²)	O(n²) substrings for preprocessing, plus partition DP transitions
Space	O(n² + kn)	Stores palindrome costs and DP states

The palindrome preprocessing requires examining all substring intervals, which takes O(n²) states. Each state performs constant work.

The partition DP has O(nk) states, and each state may try up to O(n) partition endpoints, leading to O(kn²) time overall.

Since n <= 100, this complexity easily fits within limits.

Test Cases

sol = Solution()

assert sol.palindromePartition("abc", 2) == 1
# Basic example with one required change

assert sol.palindromePartition("aabbc", 3) == 0
# Already partitionable into palindromes

assert sol.palindromePartition("leetcode", 8) == 0
# Every character forms its own palindrome

assert sol.palindromePartition("a", 1) == 0
# Single character string

assert sol.palindromePartition("aa", 1) == 0
# Already a palindrome

assert sol.palindromePartition("ab", 1) == 1
# One modification needed

assert sol.palindromePartition("abcd", 2) == 1
# Optimal split reduces total cost

assert sol.palindromePartition("abcba", 1) == 0
# Entire string already palindrome

assert sol.palindromePartition("abcdef", 3) == 2
# Multiple partitions with modifications

assert sol.palindromePartition("aaaaaa", 3) == 0
# Repeated characters

assert sol.palindromePartition("racecar", 2) == 1
# Splitting a palindrome into two parts

assert sol.palindromePartition("xyz", 1) == 1
# Entire string converted into one palindrome

Test	Why
"abc", 2	Verifies standard partitioning
"aabbc", 3	Confirms zero-cost partitions
"leetcode", 8	Tests maximum partition count
"a", 1	Smallest valid input
"aa", 1	Already palindrome
"ab", 1	Minimal modification case
"abcd", 2	Ensures optimal partition selection
"abcba", 1	Full-string palindrome
"abcdef", 3	Multiple modification paths
"aaaaaa", 3	Repeated characters
"racecar", 2	Nontrivial split handling
"xyz", 1	Odd-length palindrome conversion

Edge Cases

Case 1: k == s.length

When every character becomes its own substring, each substring is automatically a palindrome. A buggy implementation might still attempt unnecessary modifications or invalid transitions.

This implementation handles the case naturally because the DP allows partitions of length 1, whose palindrome cost is always 0.

Case 2: Entire string must remain one partition

When k == 1, the algorithm must compute the minimum modifications required for the entire string.

The preprocessing table directly supports this through:

dp[i][1] = cost[i][n-1]

This avoids any special-case logic during recursion or transitions.

Case 3: Uneven partition distributions

Some strings require highly unbalanced partitions for the optimal answer. For example, one partition may contain most of the characters while others contain single letters.

A greedy approach could fail here by choosing locally optimal palindrome substrings too early. The DP solution avoids this issue because it evaluates every possible partition endpoint before choosing the minimum total cost.