Palindrome Partitioning III — Solution in Python, Java & C++
Palindrome Partitioning III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Palindrome Partitioning III is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s of lowercase English letters and an integer k. You may first change some characters of s into other lowercase letters. Then you must split s into exactly k non-empty, non-overlapping substrings (covering all of s) so that every substring is a palindrome.
Return the minimum number of characters you need to change.
Example 1
Input: s = "abc", k = 2
Output: 1
Explanation: Split into `"ab"` and `"c"`, then change one character of `"ab"`.
Example 2
Input: s = "aabbc", k = 3
Output: 0
Explanation: `"aa"`, `"bb"`, `"c"` are already palindromes.
Example 3
Input: s = "kairo", k = 2
Output: 2
Explanation: Every split leaves two mismatched pairs, for example `"kai"` (1 change) and `"ro"` (1 change).
Constraints
1 <= k <= s.length <= 100s only contains lowercase English letters
Hints for Palindrome Partitioning III
Hint 1
The changes inside one piece do not affect any other piece. How many changes turn a fixed substring
s[i..j]into a palindrome?Hint 2
It is the number of mismatched mirror pairs:
cost[i][j] = cost[i+1][j-1] + (s[i] != s[j]). Precompute it for every substring.Hint 3
Let
dp[c][j]be the fewest changes to split the firstjcharacters intocpalindromes:dp[c][j] = min over p of dp[c-1][p] + cost[p][j-1]. The answer isdp[k][n].
How to solve Palindrome Partitioning III
Once the cut positions are fixed, each piece is fixed independently, and the cheapest fix of a piece is to change one character of every mismatched mirror pair. So precompute that cost for every substring, then choose the cuts with a partition DP.
Approach
- Fill
cost[i][j]for alli <= jby increasing length:cost[i][j] = cost[i+1][j-1] + (s[i] != s[j] ? 1 : 0), with single characters (and empty middles) costing 0. dp[0][0] = 0and every other entry is infinite.- For
cfrom 1 tokandjfromcton:dp[c][j] = min over p in [c-1, j-1] of dp[c-1][p] + cost[p][j-1]— the last piece iss[p..j-1]. - Return
dp[k][n].
Why it works
A palindrome needs s[i+t] == s[j-t] for each mirror pair, and the pairs are disjoint, so the minimum number of changes for a piece is exactly its number of mismatched pairs (one change per pair suffices and is necessary). The pieces of a split are disjoint, so the total is the sum over pieces, and the DP takes the minimum over the position of the last cut, which enumerates every split into c pieces.
Complexity
- Time —
O(k · n^2) - Space —
O(n^2 + k · n)
Pitfalls
- Each mismatched pair needs only one change, not two.
- Every piece must be non-empty: the last piece of
cpieces can start no earlier than indexc - 1. - Recomputing a piece's cost inside the partition loop makes it O(k · n^3); precompute the table.
Reference solution
Python
def palindromePartition(s: str, k: int) -> int:
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] + (1 if s[i] != s[j] else 0)
INF = float('inf')
dp = [[INF] * (n + 1) for _ in range(k + 1)]
dp[0][0] = 0
for c in range(1, k + 1):
for j in range(c, n + 1):
best = INF
for p in range(c - 1, j):
v = dp[c - 1][p] + cost[p][j - 1]
if v < best:
best = v
dp[c][j] = best
return dp[k][n]Java
public static int palindromePartition(String s, int k) {
int n = s.length();
int[][] cost = new int[n][n];
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len - 1;
cost[i][j] = cost[i + 1][j - 1] + (s.charAt(i) != s.charAt(j) ? 1 : 0);
}
}
final int INF = Integer.MAX_VALUE / 2;
int[][] dp = new int[k + 1][n + 1];
for (int[] row : dp) Arrays.fill(row, INF);
dp[0][0] = 0;
for (int c = 1; c <= k; c++) {
for (int j = c; j <= n; j++) {
int best = INF;
for (int p = c - 1; p < j; p++) best = Math.min(best, dp[c - 1][p] + cost[p][j - 1]);
dp[c][j] = best;
}
}
return dp[k][n];
}C++
int palindromePartition(string s, int k) {
int n = s.size();
vector<vector<int>> cost(n, vector<int>(n, 0));
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len - 1;
cost[i][j] = cost[i + 1][j - 1] + (s[i] != s[j] ? 1 : 0);
}
}
const int INF = INT_MAX / 2;
vector<vector<int>> dp(k + 1, vector<int>(n + 1, INF));
dp[0][0] = 0;
for (int c = 1; c <= k; c++) {
for (int j = c; j <= n; j++) {
int best = INF;
for (int p = c - 1; p < j; p++) best = min(best, dp[c - 1][p] + cost[p][j - 1]);
dp[c][j] = best;
}
}
return dp[k][n];
}JavaScript
var palindromePartition = function(s, k) {
var n = s.length, INF = Infinity;
var cost = [];
for (var i = 0; i < n; i++) cost.push(new Array(n).fill(0));
for (var len = 2; len <= n; len++) {
for (var i = 0; i + len <= n; i++) {
var j = i + len - 1;
cost[i][j] = cost[i + 1][j - 1] + (s[i] !== s[j] ? 1 : 0);
}
}
var dp = [];
for (var c = 0; c <= k; c++) dp.push(new Array(n + 1).fill(INF));
dp[0][0] = 0;
for (var c = 1; c <= k; c++) {
for (var j = c; j <= n; j++) {
var best = INF;
for (var p = c - 1; p < j; p++) best = Math.min(best, dp[c - 1][p] + cost[p][j - 1]);
dp[c][j] = best;
}
}
return dp[k][n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming