Palindrome Partitioning 3

Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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:

1
2
3
4

Input:
s = "leetcode", k = 8
Output:
 0

Solution

Method 1 – DP with Palindrome Cost Preprocessing

Intuition

We first compute the minimum number of changes needed to make any substring a palindrome. Then, we use DP to partition the string into k palindromic substrings with minimal total changes.

Approach

  1. Precompute cost[i][j]: the minimal changes to make s[i..j] a palindrome.
  2. Let dp[i][k] be the minimal changes to partition s[i:] into k palindromic substrings.
  3. For each partition, try all possible next cuts and take the minimum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int palindromePartition(string s, int K) {
        int n = s.size();
        vector<vector<int>> cost(n, vector<int>(n));
        for (int i = 0; i < n; ++i)
            for (int j = i; j < n; ++j) {
                int l = i, r = j, cnt = 0;
                while (l < r) if (s[l++] != s[r--]) ++cnt;
                cost[i][j] = cnt;
            }
        vector<vector<int>> dp(n+1, vector<int>(K+1, 1e9));
        dp[n][0] = 0;
        for (int i = n-1; i >= 0; --i)
            for (int k = 1; k <= K; ++k)
                for (int j = i; j < n; ++j)
                    dp[i][k] = min(dp[i][k], cost[i][j] + dp[j+1][k-1]);
        return dp[0][K];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func palindromePartition(s string, K int) int {
    n := len(s)
    cost := make([][]int, n)
    for i := range cost { cost[i] = make([]int, n) }
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            l, r, cnt := i, j, 0
            for l < r {
                if s[l] != s[r] { cnt++ }
                l++; r--
            }
            cost[i][j] = cnt
        }
    }
    dp := make([][]int, n+1)
    for i := range dp { dp[i] = make([]int, K+1); for k := range dp[i] { dp[i][k] = 1e9 } }
    dp[n][0] = 0
    for i := n-1; i >= 0; i-- {
        for k := 1; k <= K; k++ {
            for j := i; j < n; j++ {
                if cost[i][j]+dp[j+1][k-1] < dp[i][k] {
                    dp[i][k] = cost[i][j]+dp[j+1][k-1]
                }
            }
        }
    }
    return dp[0][K]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int palindromePartition(String s, int K) {
        int n = s.length();
        int[][] cost = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = i; j < n; ++j) {
                int l = i, r = j, cnt = 0;
                while (l < r) if (s.charAt(l++) != s.charAt(r--)) ++cnt;
                cost[i][j] = cnt;
            }
        int[][] dp = new int[n+1][K+1];
        for (int[] row : dp) Arrays.fill(row, 1000000000);
        dp[n][0] = 0;
        for (int i = n-1; i >= 0; --i)
            for (int k = 1; k <= K; ++k)
                for (int j = i; j < n; ++j)
                    dp[i][k] = Math.min(dp[i][k], cost[i][j] + dp[j+1][k-1]);
        return dp[0][K];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun palindromePartition(s: String, K: Int): Int {
        val n = s.length
        val cost = Array(n) { IntArray(n) }
        for (i in 0 until n)
            for (j in i until n) {
                var l = i; var r = j; var cnt = 0
                while (l < r) { if (s[l++] != s[r--]) cnt++ }
                cost[i][j] = cnt
            }
        val dp = Array(n+1) { IntArray(K+1) { 1_000_000_000 } }
        dp[n][0] = 0
        for (i in n-1 downTo 0)
            for (k in 1..K)
                for (j in i until n)
                    dp[i][k] = minOf(dp[i][k], cost[i][j] + dp[j+1][k-1])
        return dp[0][K]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def palindromePartition(self, s: str, K: int) -> int:
        n = len(s)
        cost = [[0]*n for _ in range(n)]
        for i in range(n):
            for j in range(i, n):
                l, r, cnt = i, j, 0
                while l < r:
                    if s[l] != s[r]: cnt += 1
                    l += 1; r -= 1
                cost[i][j] = cnt
        dp = [[float('inf')] * (K+1) for _ in range(n+1)]
        dp[n][0] = 0
        for i in range(n-1, -1, -1):
            for k in range(1, K+1):
                for j in range(i, n):
                    dp[i][k] = min(dp[i][k], cost[i][j] + dp[j+1][k-1])
        return dp[0][K]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn palindrome_partition(s: String, k: i32) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut cost = vec![vec![0; n]; n];
        for i in 0..n {
            for j in i..n {
                let (mut l, mut r, mut cnt) = (i, j, 0);
                while l < r {
                    if s[l] != s[r] { cnt += 1; }
                    l += 1; r -= 1;
                }
                cost[i][j] = cnt;
            }
        }
        let k = k as usize;
        let mut dp = vec![vec![1_000_000_000; k+1]; n+1];
        dp[n][0] = 0;
        for i in (0..n).rev() {
            for kk in 1..=k {
                for j in i..n {
                    dp[i][kk] = dp[i][kk].min(cost[i][j] + dp[j+1][kk-1]);
                }
            }
        }
        dp[0][k]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    palindromePartition(s: string, K: number): number {
        const n = s.length;
        const cost: number[][] = Array.from({length: n}, () => Array(n).fill(0));
        for (let i = 0; i < n; i++)
            for (let j = i; j < n; j++) {
                let l = i, r = j, cnt = 0;
                while (l < r) {
                    if (s[l] !== s[r]) cnt++;
                    l++; r--;
                }
                cost[i][j] = cnt;
            }
        const dp: number[][] = Array.from({length: n+1}, () => Array(K+1).fill(Infinity));
        dp[n][0] = 0;
        for (let i = n-1; i >= 0; i--)
            for (let k = 1; k <= K; k++)
                for (let j = i; j < n; j++)
                    dp[i][k] = Math.min(dp[i][k], cost[i][j] + dp[j+1][k-1]);
        return dp[0][K];
    }
}

Complexity

  • ⏰ Time complexity: O(n^3) where n is the length of the string (for cost and DP computation).
  • 🧺 Space complexity: O(n^2) for the cost and DP tables.