得到 K 个半回文串的最少修改次数

难度: Hard

给你一个字符串 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 只包含小写英文字母。

Submission

运行时间: 416 ms

内存: 21.7 MB

class Solution:
    def minimumChanges(self, s: str, k: int) -> int:
        @cache
        def get_modify(start, end):
            length = end - start + 1
            best = length
            for d in range(1, length//2+1):
                if length%d:
                    continue
                cnt = 0
                for start_ in range(d):
                    left = start + start_
                    right = end - d + start_ + 1
                    while left < right:
                        cnt += (s[left] != s[right])
                        left += d
                        right -= d
                best = min(best, cnt)
            return best
        
        @cache
        def dp(k, end):
            if k==1:
                return get_modify(0, end)
            best = 201
            for head in range((k-1)*2, end):
                best = min(best, get_modify(head, end) + dp(k-1, head-1))
            return best
        return dp(k, len(s)-1)

        # n = len(s)
        # modify = [[0] * n for _ in range(n-1)]
        # for start in range(n-1):
        #     for end in range(start+1, n):
        #         modify[start][end] = get_modify(start, end)

        # dp = [[201]*k for _ in range(n)]
        # for end in range(n):
        #     dp[end][0] = modify[0][end]
        #     for i in range(1, min(k, end//2+2)):
        #         for start in range(i*2, end):
        #             dp[end][i] = min(dp[end][i], dp[start-1][i-1] + modify[start][end])
        # return dp[-1][-1]

Explain

该题解采用了动态规划和记忆化搜索的方法来解决问题。主要分为两部分： 1. **get_modify(start, end)**: 计算将子字符串 s[start:end+1] 转换成半回文串的最小修改次数。它通过枚举所有可能的 d 值来找到最优解。对于每个 d，它检查通过分组跳跃比较字符是否能形成多个小的回文字符串。 2. **dp(k, end)**: 使用动态规划来计算最终结果，dp(k, end) 表示将字符串 s[0:end+1] 分割成 k 个半回文子字符串的最小修改次数。它递归地尝试所有可能的分割点，结合 get_modify 函数结果来更新状态。整体上，通过组合这两个函数的结果来构建全局最优解。

时间复杂度: O(n^3 * K)

空间复杂度: O(n^2 + n * K)

class Solution:
    def minimumChanges(self, s: str, k: int) -> int:
        @cache
        def get_modify(start, end):
            length = end - start + 1
            best = length  # 初始化为最大修改次数，即全部修改
            for d in range(1, length//2+1):
                if length%d:  # 如果 length 不能整除 d，跳过
                    continue
                cnt = 0
                for start_ in range(d):
                    left = start + start_
                    right = end - d + start_ + 1
                    while left < right:
                        cnt += (s[left] != s[right])
                        left += d
                        right -= d
                best = min(best, cnt)  # 取最小修改次数
            return best
        
        @cache
        def dp(k, end):
            if k==1:
                return get_modify(0, end)  # 如果只分成一个子字符串
            best = 201
            for head in range((k-1)*2, end):
                best = min(best, get_modify(head, end) + dp(k-1, head-1))
            return best
        return dp(k, len(s)-1)

Explore

在`get_modify`函数中，`length`代表考察的子字符串`s[start:end+1]`的长度。初始化最大修改次数为`length`是基于最坏情况的考虑，即如果无法通过任何方式的字符分组或调整来形成半回文串，那么可能需要修改每一个字符来达到半回文的条件。因此，最初设定`best`为`length`，然后通过尝试不同的分组方法寻找是否有需要更少修改的方案。如果有，`best`会被更新为较小的数值。

在`get_modify`函数中跳过`length % d != 0`的情况，是因为如果`length`不能被`d`整除，那么子字符串不能被平均分割成长度为`d`的多个小组。这意味着字符分组将不均匀，一些组内的字符数量会与其他组不同，从而无法通过固定的跳跃间隔进行有效的回文检查。因此，只有当`length`能被`d`整除时，才能保证所有组内的字符数量相同，这是形成多个小的回文字符串的基础。

具体来说，在计算每个可能的`d`时，通过将子字符串`s[start:end+1]`分成多个长度为`d`的小组进行处理。对于每个起始位置`start_`（从0到`d-1`），在子字符串中以`start_`为起点，每隔`d`个字符取一个，这样形成一个新的字符序列。然后，检查这个序列是否能通过最小修改成为回文串。具体检查方法是，比较序列的首尾字符，逐步向中心移动，计算不匹配的字符对，这些就是需要修改的次数。这一过程重复进行，直到覆盖所有可能的起始位置`start_`。

在`dp(k, end)`函数中，单独处理`k==1`的情况是为了效率和逻辑上的简化。当`k==1`时，意味着整个字符串`s[0:end+1]`需要被转换为一个半回文串，此时直接调用`get_modify(0, end)`得到转换整个子字符串的最小修改次数。这是一个基础情况，作为动态规划的边界条件。如果不单独处理，递归时会多一个不必要的内部循环，增加计算复杂度。单独处理可以更直接地解决问题，并减少不必要的计算。