Scale Engineer

Palindrome Partitioning III

Hard
#1192Time: Exponential. The number of ways to partition a string of length `n` into `k` parts is given by the stars and bars formula, `C(n-1, k-1)`. For each partition, we spend `O(n^2)` to calculate costs. The complexity is roughly `O(C(n-1, k-1) * n^2)`, which is too slow for the given constraints.Space: O(n) or O(k) for the recursion stack depth, where n is the length of the string.
Patterns
Dynamic Programming
Data structures
String

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach explores all possible ways to partition the string s into k non-empty substrings. For each partitioning scheme, it calculates the total number of character changes required to make every substring a palindrome and finds the minimum among all schemes. This is done using a recursive helper function that does not use memoization.

Algorithm

  • Create a helper function calculateCost(s, i, j) that computes the minimum changes to make substring s[i...j] a palindrome. It iterates from both ends inwards, counting mismatches.
  • Create a recursive function solve(s, k, index).
  • Base Case 1: If k == 1, the only option is to make the rest of the string s[index...n-1] a palindrome. Return calculateCost(s, index, n-1).
  • Base Case 2: If index >= s.length() or k <= 0, it's an invalid state, return a large value to indicate impossibility.
  • Initialize minChanges to a very large value.
  • Iterate j from index to s.length() - k. This j represents the end index of the first of the k partitions.
  • For each j, calculate currentCost = calculateCost(s, index, j).
  • Recursively call remainingCost = solve(s, k - 1, j + 1) to find the cost for the rest of the string.
  • Update minChanges = min(minChanges, currentCost + remainingCost).
  • Return minChanges.
  • The initial call to start the process is solve(s, k, 0).

Walkthrough

We define a recursive function, say solve(index, partitions_left). This function calculates the minimum cost to partition the suffix of the string starting at index into partitions_left palindromic substrings.

The base cases for the recursion are:

  • If partitions_left is 1, we must use the entire remaining string s[index...n-1] as the last partition. The cost is the number of changes to make this substring a palindrome.
  • If we run out of characters (index == n) but still need to make partitions (partitions_left > 0), or vice-versa, it's an invalid state. We return a very large value (infinity) to signify this.

In the recursive step, we try all possible split points for the current partition. We can form the first substring of the current suffix s[index...n-1] as s[index...j], where j varies from index up to a point that leaves enough characters for the remaining partitions.

For each choice of j, we calculate the cost to make s[index...j] a palindrome. Then, we recursively call the function for the rest of the string s[j+1...n-1] with partitions_left - 1.

The cost to make a substring a palindrome is calculated by comparing characters from both ends and counting the mismatches.

The function returns the minimum cost found among all possible split points j. This approach is highly inefficient because it recomputes the results for the same subproblems (same index and partitions_left) multiple times, leading to an exponential time complexity.

Complexity

Time

Exponential. The number of ways to partition a string of length `n` into `k` parts is given by the stars and bars formula, `C(n-1, k-1)`. For each partition, we spend `O(n^2)` to calculate costs. The complexity is roughly `O(C(n-1, k-1) * n^2)`, which is too slow for the given constraints.

Space

O(n) or O(k) for the recursion stack depth, where n is the length of the string.

Trade-offs

Pros

  • Conceptually simple to understand as it directly models the problem statement.

Cons

  • Extremely inefficient due to recomputing the same subproblems.

  • Will result in a 'Time Limit Exceeded' (TLE) error for most test cases due to its exponential time complexity.

Solutions

class Solution {public  int palindromePartition(String s, int k) {    int n = s.length();    int[][] g = new int[n][n];    for (int i = n - 1; i >= 0; --i) {      for (int j = i; j < n; ++j) {        g[i][j] = s.charAt(i) != s.charAt(j) ? 1 : 0;        if (i + 1 < j) {          g[i][j] += g[i + 1][j - 1];        }      }    }    int[][] f = new int[n + 1][k + 1];    for (int i = 1; i <= n; ++i) {      for (int j = 1; j <= Math.min(i, k); ++j) {        if (j == 1) {          f[i][j] = g[0][i - 1];        } else {          f[i][j] = 10000;          for (int 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];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem