class Solution {
public:
int minimumChanges(string s, int k) {
}
};
6920. 得到 K 个半回文串的最少修改次数
给你一个字符串 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 <= 2001 <= k <= s.length / 2s 只包含小写英文字母。原站题解
python3 解法, 执行用时: 3000 ms, 内存消耗: 19.1 MB, 提交时间: 2023-10-23 00:08:14
# 预处理每个数的真因子，时间复杂度 O(MX*logMX)
MX = 201
divisors = [[] for _ in range(MX)]
for i in range(1, MX):
for j in range(i * 2, MX, i):
divisors[j].append(i)
def get_modify(s: str) -> int:
res = n = len(s)
for d in divisors[n]:
cnt = 0
for i0 in range(d):
i, j = i0, n - d + i0
while i < j:
cnt += s[i] != s[j]
i += d
j -= d
res = min(res, cnt)
return res
class Solution:
def minimumChanges(self, s: str, k: int) -> int:
n = len(s)
modify = [[0] * n for _ in range(n - 1)]
for left in range(n - 1):
for right in range(left + 1, n): # 半回文串长度至少为 2
modify[left][right] = get_modify(s[left: right + 1])
@cache
def dfs(i: int, j: int) -> int:
if i == 0:
return modify[0][j]
return min(dfs(i - 1, L - 1) + modify[L][j] for L in range(i * 2, j))
return dfs(k - 1, n - 1)
class Solution2:
def minimumChanges(self, s: str, k: int) -> int:
n = len(s)
modify = [[0] * n for _ in range(n - 1)]
for left in range(n - 1):
for right in range(left + 1, n):
modify[left][right] = get_modify(s[left: right + 1])
f = modify[0]
for i in range(1, k):
for j in range(n - 1 - (k - 1 - i) * 2, i * 2, -1): # 左右都要预留空间
f[j] = min(f[L - 1] + modify[L][j] for L in range(i * 2, j))
return f[-1]
golang 解法, 执行用时: 48 ms, 内存消耗: 6.4 MB, 提交时间: 2023-10-23 00:07:34
// 预处理每个数的真因子，时间复杂度 O(mx*log(mx))
const mx = 200
var divisors [mx + 1][]int
func init() {
for i := 1; i <= mx; i++ {
for j := i * 2; j <= mx; j += i {
divisors[j] = append(divisors[j], i)
}
}
}
func calc(s string) int {
n := len(s)
res := n
for _, d := range divisors[n] {
cnt := 0
for i0 := 0; i0 < d; i0++ {
for i, j := i0, n-d+i0; i < j; i, j = i+d, j-d {
if s[i] != s[j] {
cnt++
}
}
}
res = min(res, cnt)
}
return res
}
func minimumChanges(s string, k int) (ans int) {
n := len(s)
modify := make([][]int, n-1)
for l := range modify {
modify[l] = make([]int, n)
for r := l + 1; r < n; r++ { // 半回文串长度至少为 2
modify[l][r] = calc(s[l : r+1])
}
}
memo := make([][]int, k)
for i := range memo {
memo[i] = make([]int, n)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(int, int) int
dfs = func(i, j int) int {
if i == 0 {
return modify[0][j]
}
p := &memo[i][j]
if *p != -1 {
return *p
}
res := n
for L := i * 2; L < j; L++ {
res = min(res, dfs(i-1, L-1)+modify[L][j])
}
*p = res
return res
}
return dfs(k-1, n-1)
}
func min(a, b int) int { if b < a { return b }; return a }
golang 解法, 执行用时: 44 ms, 内存消耗: 6.1 MB, 提交时间: 2023-10-23 00:07:22
const mx = 200
var divisors [mx + 1][]int
func init() {
for i := 1; i <= mx; i++ {
for j := i * 2; j <= mx; j += i {
divisors[j] = append(divisors[j], i)
}
}
}
func calc(s string) int {
n := len(s)
res := n
for _, d := range divisors[n] {
cnt := 0
for i0 := 0; i0 < d; i0++ {
for i, j := i0, n-d+i0; i < j; i, j = i+d, j-d {
if s[i] != s[j] {
cnt++
}
}
}
res = min(res, cnt)
}
return res
}
func minimumChanges(s string, k int) (ans int) {
n := len(s)
modify := make([][]int, n-1)
for l := range modify {
modify[l] = make([]int, n)
for r := l + 1; r < n; r++ {
modify[l][r] = calc(s[l : r+1])
}
}
f := modify[0]
for i := 1; i < k; i++ {
for j := n - 1 - (k-1-i)*2; j > i*2; j-- { // 左右都要预留空间
f[j] = n
for L := i * 2; L < j; L++ {
f[j] = min(f[j], f[L-1]+modify[L][j])
}
}
}
return f[n-1]
}
func min(a, b int) int { if b < a { return b }; return a }
java 解法, 执行用时: 120 ms, 内存消耗: 42.6 MB, 提交时间: 2023-10-23 00:07:02
class Solution1 {
public int minimumChanges(String s, int k) {
int n = s.length();
int[][] modify = new int[n - 1][n];
for (int left = 0; left < n - 1; left++) {
for (int right = left + 1; right < n; right++) {
modify[left][right] = getModify(s.substring(left, right + 1));
}
}
int[][] memo = new int[k][n];
for (int i = 0; i < k; i++) {
Arrays.fill(memo[i], -1); // -1 表示没有计算过
}
return dfs(k - 1, n - 1, memo, modify);
}
private static final int MX = 201;
private static final List<Integer>[] divisors = new ArrayList[MX];
static {
// 预处理每个数的真因子，时间复杂度 O(MX*logMX)
Arrays.setAll(divisors, k -> new ArrayList<>());
for (int i = 1; i < MX; i++) {
for (int j = i * 2; j < MX; j += i) {
divisors[j].add(i);
}
}
}
private int getModify(String S) {
char[] s = S.toCharArray();
int n = s.length;
int res = n;
for (int d : divisors[n]) {
int cnt = 0;
for (int i0 = 0; i0 < d; i0++) {
for (int i = i0, j = n - d + i0; i < j; i += d, j -= d) {
if (s[i] != s[j]) {
cnt++;
}
}
}
res = Math.min(res, cnt);
}
return res;
}
private int dfs(int i, int j, int[][] memo, int[][] modify) {
if (i == 0) { // 递归边界
return modify[0][j];
}
if (memo[i][j] != -1) { // 之前计算过
return memo[i][j];
}
int res = Integer.MAX_VALUE;
for (int L = i * 2; L < j; L++) {
res = Math.min(res, dfs(i - 1, L - 1, memo, modify) + modify[L][j]);
}
return memo[i][j] = res; // 记忆化
}
}
// 递推
class Solution {
public int minimumChanges(String s, int k) {
int n = s.length();
int[][] modify = new int[n - 1][n];
for (int left = 0; left < n - 1; left++) {
for (int right = left + 1; right < n; right++) {
modify[left][right] = getModify(s.substring(left, right + 1));
}
}
int[] f = modify[0];
for (int i = 1; i < k; i++) {
for (int j = n - 1 - (k - 1 - i) * 2; j > i * 2; j--) { // 左右都要预留空间
f[j] = Integer.MAX_VALUE;
for (int L = i * 2; L < j; L++) {
f[j] = Math.min(f[j], f[L - 1] + modify[L][j]);
}
}
}
return f[n - 1];
}
private static final int MX = 201;
private static final List<Integer>[] divisors = new ArrayList[MX];
static {
Arrays.setAll(divisors, k -> new ArrayList<>());
for (int i = 1; i < MX; i++) {
for (int j = i * 2; j < MX; j += i) {
divisors[j].add(i);
}
}
}
private int getModify(String S) {
char[] s = S.toCharArray();
int n = s.length;
int res = n;
for (int d : divisors[n]) {
int cnt = 0;
for (int i0 = 0; i0 < d; i0++) {
for (int i = i0, j = n - d + i0; i < j; i += d, j -= d) {
if (s[i] != s[j]) {
cnt++;
}
}
}
res = Math.min(res, cnt);
}
return res;
}
}
cpp 解法, 执行用时: 136 ms, 内存消耗: 32 MB, 提交时间: 2023-10-23 00:06:16
// 预处理每个数的真因子，时间复杂度 O(MX*logMX)
const int MX = 201;
vector<vector<int>> divisors(MX);
int init = [] {
for (int i = 1; i < MX; i++) {
for (int j = i * 2; j < MX; j += i) {
divisors[j].push_back(i);
}
}
return 0;
}();
// 记忆化搜索
class Solution {
int get_modify(string s) {
int n = s.length();
int res = n;
for (int d: divisors[n]) {
int cnt = 0;
for (int i0 = 0; i0 < d; i0++) {
for (int i = i0, j = n - d + i0; i < j; i += d, j -= d) {
cnt += s[i] != s[j];
}
}
res = min(res, cnt);
}
return res;
}
public:
int minimumChanges(string s, int k) {
int n = s.length();
vector<vector<int>> modify(n - 1, vector<int>(n));
for (int left = 0; left < n - 1; left++) {
for (int right = left + 1; right < n; right++) {
modify[left][right] = get_modify(s.substr(left, right - left + 1));
}
}
vector<vector<int>> memo(k, vector<int>(n, n + 1)); // n+1 表示没有计算过
function<int(int, int)> dfs = [&](int i, int j) -> int {
if (i == 0) {
return modify[0][j];
}
int &res = memo[i][j]; // 注意这里是引用
if (res <= n) { // 之前计算过
return res;
}
for (int L = i * 2; L < j; L++) {
res = min(res, dfs(i - 1, L - 1) + modify[L][j]);
}
return res;
};
return dfs(k - 1, n - 1);
}
};
// 递推
class Solution2 {
int get_modify(string s) {
int n = s.length();
int res = n;
for (int d: divisors[n]) {
int cnt = 0;
for (int i0 = 0; i0 < d; i0++) {
for (int i = i0, j = n - d + i0; i < j; i += d, j -= d) {
cnt += s[i] != s[j];
}
}
res = min(res, cnt);
}
return res;
}
public:
int minimumChanges(string s, int k) {
int n = s.length();
vector<vector<int>> modify(n - 1, vector<int>(n));
for (int left = 0; left < n - 1; left++) {
for (int right = left + 1; right < n; right++) {
modify[left][right] = get_modify(s.substr(left, right - left + 1));
}
}
vector<int> f(modify[0]);
for (int i = 1; i < k; i++) {
for (int j = n - 1 - (k - 1 - i) * 2; j > i * 2; j--) { // 左右都要预留空间
f[j] = INT_MAX;
for (int L = i * 2; L < j; L++) {
f[j] = min(f[j], f[L - 1] + modify[L][j]);
}
}
}
return f[n - 1];
}
};