Palindrome Partitioning III solution and explanation
6 more videos on this problem
花花酱 LeetCode 1278. Palindrome Partitioning III - 刷题找工作 EP280Hua Hua · 16:14 · 3K views
Leetcode 1278. Palindrome Partitioning III Explanation and CodeGET SDE READY · 13:19 · 2K views
5278 Palindrome Partitioning III (Weekly Contest 165)Kelvin Chandra · 4:45 · 1K views
Leetcode 1278. Palindrome Partitioning IIIFearless Learner · 10:20 · 148 views
Leetcode 1278. Palindrome Partitioning IIIAlgorithms for Big Bucks · 11:25 · 120 views
LeetCode 1278: Palindrome Partitioning IIIAlitaCode · 30:55 · 25 views
No Sound Leetcode 1278: Palindrome Partitioning IIIExtremeProgrammer · 3:54 · 9 views
The problem
You are given a string s containing lowercase letters and an integer k. You need to :
- First, change some characters of
sto other lowercase English letters. - Then divide
sintoknon-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.sonly 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.
def cost_to_make_palindrome(s, start, end):
cost = 0
while start < end:
if s[start] != s[end]:
cost += 1
start += 1
end -= 1
return cost
def palindrome_partition(s, k):
n = len(s)
dp = [[float('inf')] * (n + 1) for _ in range(k + 1)]
dp[0][0] = 0
for i in range(1, k + 1):
for j in range(1, n + 1):
for x in range(i - 1, j):
dp[i][j] = min(dp[i][j], dp[i - 1][x] + cost_to_make_palindrome(s, x, j - 1))
return dp[k][n]
print(palindrome_partition("abc", 2)) # Output: 1class Solution {
public int palindromePartition(String s, int k) {
int n = s.length();
int[][] dp = new int[k + 1][n + 1];
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = Integer.MAX_VALUE;
}
}
dp[0][0] = 0;
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= n; j++) {
for (int x = i - 1; x < j; x++) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][x] + costToMakePalindrome(s, x, j - 1));
}
}
}
return dp[k][n];
}
private int costToMakePalindrome(String s, int start, int end) {
int changes = 0;
while (start < end) {
if (s.charAt(start) != s.charAt(end)) changes++;
start++;
end--;
}
return changes;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.palindromePartition("abc", 2)); // Output: 1
}
}#include <string>
#include <vector>
#include <climits>
#include <iostream>
using namespace std;
int costToPalindrome(const string& s, int start, int end) {
int changes = 0;
while (start < end) {
if (s[start] != s[end]) changes++;
start++;
end--;
}
return changes;
}
int palindromePartition(string s, int k) {
int n = s.length();
vector<vector<int>> dp(k + 1, vector<int>(n + 1, INT_MAX));
dp[0][0] = 0;
for (int i = 1; i <= k; ++i) {
for (int j = 1; j <= n; ++j) {
for (int x = i - 1; x < j; ++x) {
dp[i][j] = min(dp[i][j], dp[i - 1][x] + costToPalindrome(s, x, j - 1));
}
}
}
return dp[k][n];
}
int main() {
cout << palindromePartition("abc", 2) << endl; // Output: 1
return 0;
}function costToMakePalindrome(s, start, end) {
let cost = 0;
while (start < end) {
if (s[start] !== s[end]) cost++;
start++;
end--;
}
return cost;
}
function palindromePartition(s, k) {
const n = s.length;
const dp = Array.from({ length: k + 1 }, () => Array(n + 1).fill(Infinity));
dp[0][0] = 0;
for (let i = 1; i <= k; i++) {
for (let j = 1; j <= n; j++) {
for (let x = i - 1; x < j; x++) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][x] + costToMakePalindrome(s, x, j - 1));
}
}
}
return dp[k][n];
}
console.log(palindromePartition("abc", 2)); // Output: 1#include <stdio.h>
#include <string.h>
#include <limits.h>
int costToMakePalindrome(char *s, int start, int end) {
int cost = 0;
while (start < end) {
if (s[start] != s[end]) cost++;
start++;
end--;
}
return cost;
}
int palindromePartition(char *s, int k) {
int n = strlen(s);
int dp[k+1][n+1];
memset(dp, sizeof(dp), 0);
for (int i = 0; i <= k; ++i) {
for (int j = 0; j <= n; ++j) {
dp[i][j] = INT_MAX;
}
}
dp[0][0] = 0;
for (int i = 1; i <= k; ++i) {
for (int j = 1; j <= n; ++j) {
for (int x = i - 1; x < j; ++x) {
dp[i][j] = fmin(dp[i][j], dp[i-1][x] + costToMakePalindrome(s, x, j - 1));
}
}
}
return dp[k][n];
}
int main() {
char s[] = "abc";
int k = 2;
printf("%d\n", palindromePartition(s, k)); // Output: 1
return 0;
}using System;
class Solution {
public int PalindromePartition(string s, int k) {
int n = s.Length;
int[,] dp = new int[k + 1, n + 1];
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= n; j++) {
dp[i, j] = int.MaxValue;
}
}
dp[0, 0] = 0;
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= n; j++) {
for (int x = i - 1; x < j; x++) {
dp[i, j] = Math.Min(dp[i, j], dp[i - 1, x] + CostToMakePalindrome(s, x, j - 1));
}
}
}
return dp[k, n];
}
private int CostToMakePalindrome(string s, int start, int end) {
int changes = 0;
while (start < end) {
if (s[start] != s[end]) changes++;
start++;
end--;
}
return changes;
}
static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.PalindromePartition("abc", 2)); // Output: 1
}
}This Python snippet employs a list of lists to act as a DP grid, similar to the other language implementations. It calculates changes and updates states iteratively.
Time Complexity: O(n^2 * k).
Space Complexity: O(n * k).
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.
def minimum_changes(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] = (s[i] != s[j]) + cost[i + 1][j - 1]
dp = [[float('inf')] * (n + 1) for _ in range(k + 1)]
dp[0][0] = 0
for g in range(1, k+1):
for i in range(g, n+1):
for j in range(g - 1, i):
dp[g][i] = min(dp[g][i], dp[g - 1][j] + cost[j][i - 1])
return dp[k][n]
print(minimum_changes("abc", 2)) # Output: 1public class PalindromePartitioning {
public static void main(String[] args) {
String s = "abc";
int k = 2;
System.out.println(minimumChanges(s, k)); // Output: 1
}
public static int minimumChanges(String s, int k) {
int n = s.length();
int[][] cost = new int[n][n];
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
cost[i][j] = (s.charAt(i) != s.charAt(j) ? 1 : 0) + cost[i + 1][j - 1];
}
}
int[][] dp = new int[k + 1][n + 1];
for (int i = 0; i <= k; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
dp[0][0] = 0;
for (int g = 1; g <= k; g++) {
for (int i = g; i <= n; i++) {
for (int j = g - 1; j < i; j++) {
dp[g][i] = Math.min(dp[g][i], dp[g - 1][j] + cost[j][i - 1]);
}
}
}
return dp[k][n];
}
}#include <string>
#include <vector>
#include <iostream>
using namespace std;
int main() {
string s = "abc";
int k = 2;
int n = s.length();
vector<vector<int>> cost(n, vector<int>(n, 0));
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1];
}
}
vector<vector<int>> dp(k + 1, vector<int>(n + 1, INT_MAX));
dp[0][0] = 0;
for (int g = 1; g <= k; ++g) {
for (int i = g; i <= n; ++i) {
for (int j = g - 1; j < i; ++j) {
dp[g][i] = min(dp[g][i], dp[g - 1][j] + cost[j][i - 1]);
}
}
}
cout << dp[k][n] << endl; // Output: 1
return 0;
}function minimumChanges(s, k) {
const n = s.length;
const cost = Array.from({ length: n }, () => Array(n).fill(0));
for (let length = 2; length <= n; length++) {
for (let i = 0; i <= n - length; i++) {
const j = i + length - 1;
cost[i][j] = (s[i] !== s[j] ? 1 : 0) + cost[i + 1][j - 1];
}
}
const dp = Array.from({ length: k + 1 }, () => Array(n + 1).fill(Infinity));
dp[0][0] = 0;
for (let g = 1; g <= k; g++) {
for (let i = g; i <= n; i++) {
for (let j = g - 1; j < i; j++) {
dp[g][i] = Math.min(dp[g][i], dp[g - 1][j] + cost[j][i - 1]);
}
}
}
return dp[k][n];
}
console.log(minimumChanges("abc", 2)); // Output: 1#include <stdio.h>
#include <string.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
int main() {
char s[] = "abc";
int k = 2;
int n = strlen(s);
int cost[n][n];
memset(cost, 0, sizeof(cost));
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1];
}
}
int dp[k + 1][n + 1];
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (int g = 1; g <= k; ++g) {
for (int i = g; i <= n; ++i) {
for (int j = g - 1; j < i; ++j) {
dp[g][i] = min(dp[g][i], dp[g - 1][j] + cost[j][i - 1]);
}
}
}
printf("%d\n", dp[k][n]); // Output: 1
return 0;
}using System;
public class Solution {
public static void Main(string[] args) {
Console.WriteLine(MinimumChanges("abc", 2)); // Output: 1
}
public static int MinimumChanges(string s, int k) {
int n = s.Length;
int[,] cost = new int[n, n];
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
cost[i, j] = (s[i] != s[j] ? 1 : 0) + cost[i + 1, j - 1];
}
}
int[,] dp = new int[k + 1, n + 1];
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= n; j++) {
dp[i, j] = int.MaxValue;
}
}
dp[0, 0] = 0;
for (int g = 1; g <= k; g++) {
for (int i = g; i <= n; i++) {
for (int j = g - 1; j < i; j++) {
dp[g, i] = Math.Min(dp[g, i], dp[g - 1, j] + cost[j, i - 1]);
}
}
}
return dp[k, n];
}
}This Python solution leverages precomputed costs for efficient DP calculation. The base and inner loops effectively determine the answer using prior cost information.
Time Complexity: O(n^2) + O(n^2 * k).
Space Complexity: O(n^2 + n * k).
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.
function palindromePartition(s: string, k: number): number {
const n = s.length;
const g: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = n - 1; i >= 0; i--) {
for (let j = i + 1; j < n; j++) {
g[i][j] = s[i] !== s[j] ? 1 : 0;
if (i + 1 < j) {
g[i][j] += g[i + 1][j - 1];
}
}
}
const f: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= Math.min(i, k); j++) {
if (j === 1) {
f[i][j] = g[0][i - 1];
} else {
f[i][j] = 1 << 30;
for (let h = j - 1; h < i; h++) {
f[i][j] = Math.min(f[i][j], f[h][j - 1] + g[h][i - 1]);
}
}
}
}
return f[n][k];
}func palindromePartition(s string, k int) int {
n := len(s)
g := make([][]int, n)
for i := range g {
g[i] = make([]int, n)
}
for i := n - 1; i >= 0; i-- {
for j := 1; j < n; j++ {
if s[i] != s[j] {
g[i][j] = 1
}
if i+1 < j {
g[i][j] += g[i+1][j-1]
}
}
}
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, k+1)
}
for i := 1; i <= n; i++ {
for j := 1; j <= min(i, k); j++ {
if j == 1 {
f[i][j] = g[0][i-1]
} else {
f[i][j] = 100000
for h := j - 1; h < i; h++ {
f[i][j] = min(f[i][j], f[h][j-1]+g[h][i-1])
}
}
}
}
return f[n][k]
}impl Solution {
pub fn palindrome_partition(s: String, k: i32) -> i32 {
let n = s.len();
let s: Vec<char> = s.chars().collect();
let mut g = vec![vec![0; n]; n];
for i in (0..n).rev() {
for j in i + 1..n {
g[i][j] = if s[i] != s[j] { 1 } else { 0 };
if i + 1 < j {
g[i][j] += g[i + 1][j - 1];
}
}
}
let mut f = vec![vec![0; (k + 1) as usize]; n + 1];
let inf = i32::MAX;
for i in 1..=n {
for j in 1..=i.min(k as usize) {
if j == 1 {
f[i][j] = g[0][i - 1];
} else {
f[i][j] = inf;
for h in (j - 1)..i {
f[i][j] = f[i][j].min(f[h][j - 1] + g[h][i - 1]);
}
}
}
}
f[n][k as usize]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with 2D Arrays | Time Complexity: O(n^2 * k). |
| Dynamic Programming with Auxiliary Cost Calculation | Time Complexity: O(n^2) + O(n^2 * k). |
| Dynamic Programming | – |
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 |
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).