Palindrome Partitioning III

Hard
1523.

Palindrome Partitioning III

Palindrome Partitioning III is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

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 <= 100
  • s only contains lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var palindromePartition = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • s only contains lowercase English letters

Hints for Palindrome Partitioning III

  1. 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?

  2. 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.

  3. Hint 3

    Let dp[c][j] be the fewest changes to split the first j characters into c palindromes: dp[c][j] = min over p of dp[c-1][p] + cost[p][j-1]. The answer is dp[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

  1. Fill cost[i][j] for all i <= j by increasing length: cost[i][j] = cost[i+1][j-1] + (s[i] != s[j] ? 1 : 0), with single characters (and empty middles) costing 0.
  2. dp[0][0] = 0 and every other entry is infinite.
  3. For c from 1 to k and j from c to n: dp[c][j] = min over p in [c-1, j-1] of dp[c-1][p] + cost[p][j-1] — the last piece is s[p..j-1].
  4. 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 c pieces can start no earlier than index c - 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