Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1278. Palindrome Partitioning III - Leetcode Solution

Code Implementation

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        # Precompute the cost to make s[i:j+1] a palindrome
        cost = [[0]*n for _ in range(n)]
        for l in range(2, n+1):
            for i in range(n-l+1):
                j = i + l - 1
                cost[i][j] = cost[i+1][j-1] + (0 if s[i] == s[j] else 1)

        # dp[i][kk]: min cost to split s[i:] into kk parts
        from functools import lru_cache
        @lru_cache(None)
        def dp(i, kk):
            if n - i == kk:
                return 0  # Each char is a palindrome
            if kk == 1:
                return cost[i][n-1]
            res = float('inf')
            for j in range(i, n-kk+1):
                res = min(res, cost[i][j] + dp(j+1, kk-1))
            return res

        return dp(0, k)
      
class Solution {
public:
    int palindromePartition(string s, int k) {
        int n = s.size();
        vector<vector<int>> cost(n, vector<int>(n, 0));
        // Precompute cost to make s[i..j] palindrome
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                cost[i][j] = cost[i+1][j-1] + (s[i] != s[j]);
            }
        }
        // dp[i][kk]: min cost to split s[i:] into kk parts
        vector<vector<int>> dp(n+1, vector<int>(k+1, INT_MAX/2));
        for (int i = 0; i <= n; ++i) dp[i][0] = INT_MAX/2;
        for (int i = 0; i <= n; ++i) dp[i][1] = (i < n) ? cost[i][n-1] : 0;

        for (int kk = 2; kk <= k; ++kk) {
            for (int i = 0; i <= n-kk; ++i) {
                for (int j = i; j <= n-kk; ++j) {
                    dp[i][kk] = min(dp[i][kk], cost[i][j] + dp[j+1][kk-1]);
                }
            }
        }
        return dp[0][k];
    }
};
      
class Solution {
    public int palindromePartition(String s, int k) {
        int n = s.length();
        int[][] cost = new int[n][n];
        // Precompute cost to make s[i..j] palindrome
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                cost[i][j] = cost[i+1][j-1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
            }
        }
        int[][] dp = new int[n+1][k+1];
        for (int i = 0; i <= n; ++i) {
            for (int kk = 0; kk <= k; ++kk) {
                dp[i][kk] = Integer.MAX_VALUE / 2;
            }
        }
        for (int i = 0; i <= n; ++i) dp[i][1] = (i < n) ? cost[i][n-1] : 0;

        for (int kk = 2; kk <= k; ++kk) {
            for (int i = 0; i <= n-kk; ++i) {
                for (int j = i; j <= n-kk; ++j) {
                    dp[i][kk] = Math.min(dp[i][kk], cost[i][j] + dp[j+1][kk-1]);
                }
            }
        }
        return dp[0][k];
    }
}
      
var palindromePartition = function(s, k) {
    const n = s.length;
    // Precompute cost to make s[i..j] palindrome
    const cost = Array.from({length: n}, () => Array(n).fill(0));
    for (let len = 2; len <= n; ++len) {
        for (let i = 0; i + len - 1 < n; ++i) {
            let j = i + len - 1;
            cost[i][j] = cost[i+1][j-1] + (s[i] === s[j] ? 0 : 1);
        }
    }
    // dp[i][kk]: min cost to split s[i:] into kk parts
    const dp = Array.from({length: n+1}, () => Array(k+1).fill(Infinity));
    for (let i = 0; i <= n; ++i) dp[i][1] = (i < n) ? cost[i][n-1] : 0;

    for (let kk = 2; kk <= k; ++kk) {
        for (let i = 0; i <= n - kk; ++i) {
            for (let j = i; j <= n - kk; ++j) {
                dp[i][kk] = Math.min(dp[i][kk], cost[i][j] + dp[j+1][kk-1]);
            }
        }
    }
    return dp[0][k];
};

Problem Description

Given a string s and an integer k, split s into k non-empty, contiguous substrings. You must change the minimum number of characters in s so that every substring is a palindrome. Return the minimum number of character changes needed.
  • Each substring must be non-empty and contiguous.
  • You must split s into exactly k parts.
  • You are allowed to change any character to any other character.
  • Return the minimum number of changes required so that every substring is a palindrome.
Constraints:
  • 1 <= k <= s.length <= 100
  • s consists of lowercase English letters.

Thought Process

At first glance, the problem seems to require checking all possible ways to split the string into k parts and, for each split, calculating how many character changes are needed for each part to become a palindrome. This brute-force approach would involve:
  • Trying all possible ways to split the string into k parts (which is exponential in nature), and
  • For each split, checking each substring and counting the minimum changes needed to make it a palindrome.
However, this is computationally expensive and not feasible for larger strings. To optimize:
  • We notice that the cost to make any substring a palindrome can be precomputed.
  • We can use dynamic programming to avoid recomputation and efficiently find the minimal changes needed for all splits.
The key is to break the problem into smaller subproblems, solve them efficiently, and build up the solution.

Solution Approach

We use a two-stage dynamic programming approach:
  1. Precompute Palindrome Change Costs:
    • For every substring s[i:j], calculate the minimum number of changes needed to make it a palindrome.
    • This is done by comparing characters from the ends towards the center, counting mismatches.
    • We store these costs in a 2D array cost[i][j].
  2. Dynamic Programming for Partitioning:
    • Let dp[i][kk] represent the minimum changes needed to partition s[i:] into kk palindromic substrings.
    • The recurrence is:
      • If kk == 1: dp[i][1] = cost[i][n-1] (the whole remaining string is one part).
      • Otherwise, try every possible split point j (where the first part is s[i:j]), and set:
        dp[i][kk] = min(cost[i][j] + dp[j+1][kk-1]) for all valid j.
    • Build the solution from the end of the string towards the start, filling the DP table.
    • The answer is dp[0][k].
This approach ensures we only compute each subproblem once and reuse results, making it efficient.

Example Walkthrough

Example: s = "abc", k = 2
  • Possible splits: ["a", "bc"], ["ab", "c"]
  • For ["a", "bc"]:
    • "a" is already a palindrome (0 changes).
    • "bc": needs 1 change ('b' to 'c' or 'c' to 'b').
    • Total changes: 1
  • For ["ab", "c"]:
    • "ab": needs 1 change ('a' to 'b' or 'b' to 'a').
    • "c" is already a palindrome (0 changes).
    • Total changes: 1
  • So the minimum number of changes required is 1.
  • The DP table will fill cost[0][0]=0, cost[0][1]=1, cost[1][2]=1, etc., and the recursive DP will select the minimum.

Time and Space Complexity

  • Brute-force Approach:
    • Trying all possible splits is exponential: O(2n).
  • Optimized DP Approach:
    • Precomputing palindrome costs: O(n2).
    • DP for partitioning: For each of O(nk) states, we may try up to O(n) split points, so O(n2k).
    • Total time complexity: O(n2k)
    • Space complexity: O(n2) for the cost table and O(nk) for the DP table.

Summary

We solved Palindrome Partitioning III by first precomputing the minimum changes needed to make any substring a palindrome, then using dynamic programming to efficiently find the optimal way to split the string into k palindromic parts. This approach avoids redundant computation, leverages overlapping subproblems, and turns an exponential problem into a polynomial one. The elegance comes from precomputing costs and using DP to build the solution step by step.