2911. 得到 K 个半回文串的最少修改次数(2608)

给你一个字符串 s 和一个整数 k ，请你将 s 分成 k 个 子字符串 ，使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。

请你返回一个整数，表示需要修改的 最少 字符数目。

注意：

  • 如果一个字符串从左往右和从右往左读是一样的，那么它是一个 回文串 。
  • 如果长度为 len 的字符串存在一个满足 1 <= d < len 的正整数 d ，len % d == 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 ，那么我们说这个字符串是 半回文串 。比方说 "aa" ，"aba" ，"adbgad" 和 "abab" 都是 半回文串 ，而 "a" ，"ab" 和 "abca" 不是。
  • 子字符串 指的是一个字符串中一段连续的字符序列。

示例 1：

1
2
3
4
输入：s = "abcac", k = 2
输出：1
解释：我们可以将 s 分成子字符串 "ab" 和 "cac" 。子字符串 "cac" 已经是半回文串。如果我们将 "ab" 变成 "aa" ，它也会变成一个 d = 1 的半回文串。
该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 1 。

示例 2:

1
2
3
4
输入：s = "abcdef", k = 2
输出：2
解释：我们可以将 s 分成子字符串 "abc" 和 "def" 。子字符串 "abc" 和 "def" 都需要修改一个字符得到半回文串，所以我们总共需要 2 次字符修改使所有子字符串变成半回文串。
该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 2 。

示例 3：

1
2
3
4
输入：s = "aabbaa", k = 3
输出：0
解释：我们可以将 s 分成子字符串 "aa" ，"bb" 和 "aa" 。
字符串 "aa" 和 "bb" 都已经是半回文串了。所以答案为 0 。

提示：

  • 2 <= s.length <= 200
  • 1 <= k <= s.length / 2
  • s 只包含小写英文字母。
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
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int minimumChanges(String s, int k) {
        char[] cs = s.toCharArray();
        int n = cs.length, costs[][] = new int[n][n], inf = (int)1e9;
        // 计算所有子串的costs信息（子串变成半回文串的最小花费）
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {  // s[i:j]
                int len = j - i + 1;
                costs[i][j] = inf;
                for (int d = 1; d < len; d++) {
                    if (len % d != 0) continue;
                    int cost = 0;
                    for (int l = i; l < i + d; l++) {
                        int r = j - j % d + l % d;
                        if (r > j) r -= d;
                        int ll = l, rr = r;
                        while (ll < rr) {
                            if (cs[ll] != cs[rr]) cost++;
                            ll += d; rr -= d;
                        }
                    }
                    costs[i][j] = Math.min(costs[i][j], cost);
                }
            }
        }
        // dp[i][j]: 在[0:i)的子串中划分j次的最少修改字符数目
        int dp[][] = new int[n+1][k+1];
        for (int row[] : dp) Arrays.fill(row, inf);
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                for (int pre = 0; pre < i; pre++) {
                    dp[i+1][j+1] = Math.min(dp[i+1][j+1], dp[pre][j] + costs[pre][i]);
                }
            }
        }
        return dp[n][k];
    }
}