Palindrome Partitioning III - Solution & Explanation

Q: Is Palindrome Partitioning III easy or hard?

Palindrome Partitioning III is categorized as a Hard problem because it combines substring preprocessing with multi‑state dynamic programming. Efficient solutions require recognizing overlapping subproblems and optimizing repeated palindrome cost calculations.

Q: Palindrome Partitioning III Python/Java solution

Python and Java implementations follow the same strategy: compute a cost matrix for all substrings, then run a DP loop over partition counts and string indices. Both languages typically store results in 2D arrays and iterate over split points to update the minimum cost.

Q: How to solve Palindrome Partitioning III in O(n^2 * k)?

Precompute a cost matrix where cost[i][j] stores how many character replacements are needed to make s[i..j] a palindrome. Then use dynamic programming where dp[i][p] is the minimum cost to partition the prefix ending at i into p palindromes. For each state, iterate possible split points and combine dp values with the precomputed cost.

Q: What is the best approach for Palindrome Partitioning III?

The most efficient approach uses dynamic programming with a precomputed palindrome cost table. First compute cost[i][j], the number of character changes needed to convert substring s[i..j] into a palindrome in O(n^2). Then use DP where dp[i][k] represents the minimum cost to split the first i characters into k palindromes, resulting in O(n^2 * k) total time.

Q: Is Palindrome Partitioning III asked at Google/Amazon/Meta?

Palindrome partitioning and string DP problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that involve splitting strings into palindromes or minimizing modifications test understanding of dynamic programming over substrings.

Q: What data structure is used in Palindrome Partitioning III?

The solution primarily uses 2D arrays for dynamic programming tables. One matrix stores the cost of converting substrings into palindromes, and another DP table tracks the minimum modification cost for partitioning the string into k segments.

Q: What is the time complexity of Palindrome Partitioning III?

The optimized dynamic programming solution runs in O(n^2 * k) time after an O(n^2) preprocessing step for palindrome costs. A simpler implementation that calculates substring palindrome costs during transitions can degrade to O(n^3). Space complexity is typically O(n^2 + n*k).

HardString Dynamic Programming22 min read

Practice this problem

Problem Statement

You are given a string s containing lowercase letters and an integer k. You need to :

First, change some characters of s to other lowercase English letters.
Then divide 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.

Approach Overview

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 1: Dynamic Programming with 2D Arrays

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2 * k), where n is the length of the string.
Space Complexity: O(n * k) due to the DP table.

Try this approach in the editor →

Approach 2: Dynamic Programming with Auxiliary Cost Calculation

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2) for preprocessing cost table + O(n^2 * k) for DP.
Space Complexity: O(n^2 + n * k).

Try this approach in the editor →

Approach 3: 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].

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.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Dynamic Programming with 2D Arrays	Time Complexity: O(n^2 * k), where n is the length of the string. Space Complexity: O(n * k) due to the DP table.
Dynamic Programming with Auxiliary Cost Calculation	Time Complexity: O(n^2) for preprocessing cost table + O(n^2 * k) for DP. Space Complexity: O(n^2 + n * k).
Dynamic Programming	—

Detailed Complexity Analysis

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

Video Solution

花花酱 LeetCode 1278. Palindrome Partitioning III - 刷题找工作 EP280 • Hua Hua • 3,396 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Palindrome Partitioning III easy or hard?

Palindrome Partitioning III is categorized as a Hard problem because it combines substring preprocessing with multi‑state dynamic programming. Efficient solutions require recognizing overlapping subproblems and optimizing repeated palindrome cost calculations.

Palindrome Partitioning III Python/Java solution

Python and Java implementations follow the same strategy: compute a cost matrix for all substrings, then run a DP loop over partition counts and string indices. Both languages typically store results in 2D arrays and iterate over split points to update the minimum cost.

How to solve Palindrome Partitioning III in O(n^2 * k)?

Precompute a cost matrix where cost[i][j] stores how many character replacements are needed to make s[i..j] a palindrome. Then use dynamic programming where dp[i][p] is the minimum cost to partition the prefix ending at i into p palindromes. For each state, iterate possible split points and combine dp values with the precomputed cost.

What is the best approach for Palindrome Partitioning III?

The most efficient approach uses dynamic programming with a precomputed palindrome cost table. First compute cost[i][j], the number of character changes needed to convert substring s[i..j] into a palindrome in O(n^2). Then use DP where dp[i][k] represents the minimum cost to split the first i characters into k palindromes, resulting in O(n^2 * k) total time.

Is Palindrome Partitioning III asked at Google/Amazon/Meta?

Palindrome partitioning and string DP problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that involve splitting strings into palindromes or minimizing modifications test understanding of dynamic programming over substrings.

What data structure is used in Palindrome Partitioning III?

The solution primarily uses 2D arrays for dynamic programming tables. One matrix stores the cost of converting substrings into palindromes, and another DP table tracks the minimum modification cost for partitioning the string into k segments.

What is the time complexity of Palindrome Partitioning III?

The optimized dynamic programming solution runs in O(n^2 * k) time after an O(n^2) preprocessing step for palindrome costs. A simpler implementation that calculates substring palindrome costs during transitions can degrade to O(n^3). Space complexity is typically O(n^2 + n*k).

Ready to solve this problem?

Practice Palindrome Partitioning III with our built-in code editor and test cases.

Practice on FleetCode

Maximum Number of Non-overlapping Palindrome Substrings

Minimum Changes to Make K Semi-palindromes

Problem Info

DifficultyHard

Acceptance62.2%

Approaches3

Reading time22 min

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Dynamic Programming with 2D Arrays

Code

Complexity

Approach 2: Dynamic Programming with Auxiliary Cost Calculation

Code

Complexity

Approach 3: Dynamic Programming

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents