题目:
给你一个字符串 s 和一个整数 k ,请你将 s 分成 k 个 子字符串 ,使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
请你返回一个整数,表示需要修改的 最少 字符数目。
注意:
如果一个字符串从左往右和从右往左读是一样的,那么它是一个 回文串 。
如果长度为 len 的字符串存在一个满足 1 <= d < len 的正整数 d ,len % d == 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 ,那么我们说这个字符串是 半回文串 。比方说 “aa” ,“aba” ,“adbgad” 和 “abab” 都是 半回文串 ,而 “a” ,“ab” 和 “abca” 不是。
子字符串 指的是一个字符串中一段连续的字符序列。
示例 1:
输入:s = “abcac”, k = 2
输出:1
解释:我们可以将 s 分成子字符串 “ab” 和 “cac” 。子字符串 “cac” 已经是半回文串。如果我们将 “ab” 变成 “aa” ,它也会变成一个 d = 1 的半回文串。
该方案是将 s 分成 2 个子字符串的前提下,得到 2 个半回文子字符串需要的最少修改次数。所以答案为 1 。
示例 2:
输入:s = “abcdef”, k = 2
输出:2
解释:我们可以将 s 分成子字符串 “abc” 和 “def” 。子字符串 “abc” 和 “def” 都需要修改一个字符得到半回文串,所以我们总共需要 2 次字符修改使所有子字符串变成半回文串。
该方案是将 s 分成 2 个子字符串的前提下,得到 2 个半回文子字符串需要的最少修改次数。所以答案为 2 。
示例 3:
输入:s = “aabbaa”, k = 3
输出:0
解释:我们可以将 s 分成子字符串 “aa” ,“bb” 和 “aa” 。
字符串 “aa” 和 “bb” 都已经是半回文串了。所以答案为 0 。
提示:
2 <= s.length <= 200
1 <= k <= s.length / 2
s 只包含小写英文字母。
java代码:
class Solution {
char[] chars;
int[][] dps;
int[][] checks;
public int minimumChanges(String s, int k) {
this.chars = s.toCharArray();
final int n = chars.length;
this.dps = new int[n][k + 1];
this.checks = new int[n][n];
return dp(0, k) - k;
}
private int checkD(int head, int tail, int d) {
final int length = tail - head + 1;
int res = 0;
for (int x = 0; x < d; x++) {
for (int left = head + x, right = left + length - d; left < right; left += d, right -= d) {
if (chars[left] != chars[right]) res++;
}
}
return res;
}
private int check(int head, int tail) {
if (checks[head][tail] > 0) return checks[head][tail];
int length = tail - head + 1;
int sq = (int)Math.sqrt(length);
int best = checkD(head, tail, 1);
for (int d = 2; d <= sq; d++) {
if (length % d > 0) continue;
best = Math.min(best, checkD(head, tail, d));
best = Math.min(best, checkD(head, tail, length / d));
}
return checks[head][tail] = best + 1;
}
private int dp(int head, int k) {
if (k == 1) return check(head, chars.length - 1);
if (dps[head][k] > 0) return dps[head][k];
final int end = chars.length - (k - 1) * 2;
int best = Integer.MAX_VALUE;
for (int tail = head + 1; tail < end; tail++) {
int res = check(head, tail) + dp(tail + 1, k - 1);
best = Math.min(best, res);
}
return dps[head][k] = best;
}
}