DeepSeek LeetCode 2911. 得到 K 个半回文串的最少修改次数 TypeScript实现
以下是 LeetCode 2911 题「得到 K 个半回文串的最少修改次数」的 TypeScript 实现，包含完整的类型定义和详细的注释。
```typescript
/**
* 计算将字符串 s 分成 k 个半回文子串所需的最少修改次数
* @param s 原始字符串
* @param k 需要分成的子串数目
* @returns 最少修改次数
*/
function minimumChanges(s: string, k: number): number {
const n: number = s.length;
// ---------- 1. 预处理 cost[l][r]：子串 s[l..r] 变成半回文的最小修改次数 ----------
const cost: number[][] = Array.from({ length: n }, () => Array(n).fill(Infinity));
// 枚举所有子串
for (let l = 0; l < n; l++) {
for (let r = l; r < n; r++) {
const len: number = r - l + 1;
if (len < 2) continue; // 长度至少为 2 才能成为半回文
let best: number = Infinity;
// 枚举 len 的所有真因子 d (1 <= d < len 且 len % d === 0)
for (let d = 1; d < len; d++) {
if (len % d !== 0) continue;
let changes: number = 0;
// 遍历 d 个轨道，每个轨道的起点偏移 start = 0 .. d-1
for (let start = 0; start < d; start++) {
// 该轨道的字符下标：l+start, l+start+d, l+start+2d, ...
// 双指针从两端向中间比较
let i: number = l + start;
let j: number = l + start + Math.floor((len - 1 - start) / d) * d;
while (i < j) {
if (s[i] !== s[j]) changes++;
i += d;
j -= d;
}
}
best = Math.min(best, changes);
}
cost[l][r] = best;
}
}
// ---------- 2. 动态规划：将前 i 个字符分成 c 段的最小代价 ----------
// dp[i][c] 表示 s[0..i-1] 分成 c 段的最小修改次数
const dp: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(Infinity));
dp[0][0] = 0; // 空串分成 0 段代价为 0
for (let c = 1; c <= k; c++) {
for (let i = c; i <= n; i++) {
// 枚举最后一段的起始位置 j（前 j 个字符已经分成 c-1 段）
for (let j = c - 1; j < i; j++) {
if (dp[j][c - 1] !== Infinity && cost[j][i - 1] !== Infinity) {
dp[i][c] = Math.min(dp[i][c], dp[j][c - 1] + cost[j][i - 1]);
}
}
}
}
return dp[n][k];
}
```
核心思路说明
1. 半回文串的判断与最小修改
· 定义：长度为 L 的字符串，若存在一个真因子 d（1 ≤ d < L 且 L % d == 0），使得将所有下标按模 d 分组后，每组都是回文串，则称为半回文。
· 最小修改计算：
· 对于每个可行的 d，将原串划分为 d 条轨道（每条轨道由间隔 d 的下标组成）。
· 对每条轨道使用双指针从两端向中间比较，统计不相等的字符对数。
· 所有轨道的对数之和即为按该 d 划分需要的修改次数。
· 取所有 d 中的最小值作为该子串的半回文最小修改代价。
2. 预处理 cost 数组
· 枚举所有子串 s[l..r]，计算其最小修改次数，结果存入 cost[l][r]。
· 复杂度 O(n³)，在 n ≤ 200 时可接受（约 800 万次操作）。
3. 动态规划划分
· dp[i][c]：前 i 个字符（s[0..i-1]）分成 c 段的最小修改次数。
· 转移方程：
dp[i][c] = min( dp[j][c-1] + cost[j][i-1] )，其中 c-1 ≤ j < i。
· 初始状态：dp[0][0] = 0，其余为无穷大。
· 最终答案：dp[n][k]。
4. 边界与优化
· 若 k > n，理论上无法分割（题目保证不会出现此类情况）。
· 长度小于 2 的子串无法成为半回文，cost 保留 Infinity，DP 时会自动跳过非法划分。
复杂度分析
· 时间：预处理 O(n³)，DP O(n²·k)。
· 空间：O(n² + n·k)，其中 cost 数组占 O(n²)，dp 表占 O(n·k)。
测试示例
```typescript
// 示例 1
console.log(minimumChanges("abcde", 2)); // 输出: 2
// 示例 2
console.log(minimumChanges("aabbaa", 3)); // 输出: 0
```
如需进一步解释半回文定义或优化细节，欢迎继续提问！