Minimum Changes to Make K Semi-palindromes

Given a string s and an integer k, partition s into k substrings such that the sum of the number of letter changes required to turn each substring into a semi-palindrome is minimized.

Return an integer denoting the minimum number of letter changes required.

Notes

A string is a palindrome if it can be read the same way from left to right and right to left.
A string with a length of len is considered a semi-palindrome if there exists a positive integer d such that 1 <= d < len and len % d == 0, and if we take indices that have the same modulo by d, they form a palindrome. For example, "aa", "aba", "adbgad", and, "abab" are semi-palindrome and "a", "ab", and, "abca" are not.
A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "abcac", k = 2
Output: 1
Explanation: We can divide s into substrings "ab" and "cac". The string "cac" is already a semi-palindrome. If we change "ab" to "aa", it becomes a semi-palindrome with d = 1.
It can be shown that there is no way to divide the string "abcac" into two semi-palindrome substrings. Therefore, the answer would be at least 1.

Example 2:

Input: s = "abcdef", k = 2
Output: 2
Explanation: We can divide it into substrings "abc" and "def". Each of the substrings "abc" and "def" requires one change to become a semi-palindrome, so we need 2 changes in total to make all substrings semi-palindrome.
It can be shown that we cannot divide the given string into two substrings in a way that it would require less than 2 changes.

Example 3:

Input: s = "aabbaa", k = 3
Output: 0
Explanation: We can divide it into substrings "aa", "bb" and "aa".
The strings "aa" and "bb" are already semi-palindromes. Thus, the answer is zero.

Constraints:

2 <= s.length <= 200
1 <= k <= s.length / 2
s consists only of lowercase English letters.

解题思路

比赛的时候被傻逼第三题卡了快一个小时，导致没多少时间写这题，事实上这题比第三题简单多了，不过代码调了蛮久，而且有个特别坑的地方，就是长度为 $1$ 的子串不是半回文串！因为给出了 $1 \leq d < |s|$ 的条件。补题的时候被这个地方卡了半天，md绝了。

首先一眼 dp，定义 $f(i,j)$ 表示将前 $i$ 个字符划分为 $j$ 个半回文子串的所有方案中修改次数的最小值，根据最后一段子串（以 $i$ 为右端点的子串）的左端点 $k$ 进行状态划分，因此有状态转移方程 $f(i, j) = \min\limits_{1 \leq k < i} \left\{ f(k-1, j-1) + g(k, i) \right\}$。

其中 $g(i, j)$ 是指将 $s$ 的子串 $s[i \sim j]$ 变成半回文串所需要的最小修改次数。直接暴力算就好了，分别枚举左右端点 $i$ 和 $j$，然后对子串的长度 $\text{len} = j-i+1$ 分解约数 $d$，如果 $d \mid \text{len}$，那么提取子串中相应的位置（模 $d$ 相同的下标），计算把这些位置构成的串变成回文串的最小修改次数（若两端的字符不一样就要对其中一个修改一次）。对所有满足条件的 $d$ 计算修改次数，取最小值，就是 $g(i,j)$ 的值。

我们知道求 $1 \sim n$ 中每个数的约数可以用类似线性筛的做法求，时间复杂度是 $O(n \log{n})$，意味着平均下来 $1 \sim n$ 每个数大概有 $\log{n}$ 个约数。因此上述做法的时间复杂度是 $O(n^2 (\sqrt{n} + n \log{n}))$。如果一开始把每个数的约数都预处理出来，那么时间复杂度就优化到 $O(n^3 \log{n})$。

dp 的时间复杂度是 $O(n^2 m)$，因此总的时间复杂度就是 $O(n^3 \log{n})$。

AC 代码如下：

class Solution {
public:
    int minimumChanges(string s, int m) {
        int n = s.size();
        vector<vector<int>> p(n + 1);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                if (i % j == 0) {
                    p[i].push_back(j);
                    if (j > 1 && i / j != j) p[i].push_back(i / j);
                }
            }
        }
        vector<vector<int>> g(n + 1, vector<int>(n + 1, 0x3f3f3f3f));
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                function<int(int)> get = [&](int x) {
                    int cnt = 0;
                    for (int u = 0; u < x; u++) {
                        string t;
                        for (int v = i + u; v <= j; v += x) {
                            t += s[v - 1];
                        }
                        for (int l = 0, r = t.size() - 1; l < r; l++, r--) {
                            if (t[l] != t[r]) cnt++;
                        }
                    }
                    return cnt;
                };
                for (auto &x : p[j - i + 1]) {
                    g[i][j] = min(g[i][j], get(x));
                }
            }
        } 
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0x3f3f3f3f));
        f[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 1; k < i; k++) {
                    f[i][j] = min(f[i][j], f[k - 1][j - 1] + g[k][i]);
                }
            }
        }
        return f[n][m];
    }
};