如何用动态规划优化至多改1字符的字符串最大分割次数问题？

状态定义 #

定义二维数组 dp[i][j]：

• i 表示已处理完字符串的前 i 个字符（前 i 位已被分割删除）
• j 表示已使用的修改次数（仅能取 0 或 1，因为最多允许修改1次）
• dp[i][j] 的值为前 i 个字符能分割出的最大子串数量

初始状态：

• dp[0][0] = 0（未处理任何字符、未使用修改机会，分割数为0）
• dp[0][1] = 0（未处理字符但预留修改机会，分割数为0）
• 其余 dp[i][j] 初始化为负无穷（表示该状态不可达）

预处理最长子串长度 #

为高效完成状态转移，先预处理两个数组：

1. max_len0[i] #

表示从第 i 个字符开始，不修改任何字符时，能选取的最长、至多包含 K 个不同字符的子串长度。
用滑动窗口实现：

• 维护窗口内字符的计数哈希表，左边界从 i 开始，右边界尽可能向右扩展
• 当窗口内不同字符数超过 K 时停止，此时窗口长度即为 max_len0[i]
• 优化：右边界无需每次从 i 重新开始，可延续上一次的右边界，整体时间复杂度 O(N)

2. max_len1[i] #

表示从第 i 个字符开始，允许修改1个字符时，能选取的最长、至多包含 K 个不同字符的子串长度。
同样用滑动窗口实现：

• 维护字符计数哈希表，同时记录是否已使用修改机会
• 当窗口内不同字符数超过 K 时，尝试将一个非主要字符集中的字符修改为已有的字符（消耗一次修改机会），继续扩展右边界
• 最终得到的窗口长度即为 max_len1[i]，时间复杂度 O(N)

状态转移 #

遍历每个处理位置 i 和修改状态 j，执行状态转移：

• 当 j=0（未使用修改机会）：
  • 若 dp[i][0] 可达（非负无穷）：
    • 选择不修改：取 l = max_len0[i]，更新 dp[i+l][0] = max(dp[i+l][0], dp[i][0] + 1)
    • 选择使用修改机会：取 l = max_len1[i]，更新 dp[i+l][1] = max(dp[i+l][1], dp[i][0] + 1)
• 当 j=1（已使用修改机会）：
  • 若 dp[i][1] 可达：
    • 仅能选择不修改：取 l = max_len0[i]，更新 dp[i+l][1] = max(dp[i+l][1], dp[i][1] + 1)

最终答案 #

处理完所有字符后，取 max(dp[N][0], dp[N][1])，即为能分割出的最大子串数量。

复杂度分析 #

• 预处理阶段：O(N)
• 动态规划阶段：O(N)
• 整体时间复杂度 O(N)，相比暴力解法的 O(N²) 大幅优化

内容的提问来源于stack exchange，提问作者Jox