如何编写函数删除字符串内的回文子串以得到最短可行字符串

首先这个问题无法通过贪心策略（例如每次优先删除最长回文子串）得到全局最优解，你给出的示例已经验证了这点：

给定字符串“lolahal”，如果先删除最大的回文子串“lahal”，最终会剩余长度为2的字符串“lo”；如果先删除“lol”、再删除“aha”，最终就能得到预期的最优结果，即长度为1的字符串“l”。

要得到最优解，标准方案是使用区间动态规划，思路和实现如下： #

核心思路 #

我们用区间DP遍历所有子串的可能删除顺序，记录每个区间能得到的最短结果：

• 定义dp[i][j]为删除字符串下标i到j（闭区间）的所有回文子串后，能得到的最短字符串长度
• 边界条件：
  • 当i > j时，区间为空，dp[i][j] = 0
  • 当i == j时，区间只有单个字符，无法继续删除，dp[i][j] = 1
• 状态转移规则：
  1. 如果s[i] == s[j]，当区间i+1到j-1最终被删到只剩1个字符时，可与两端的相同字符组成回文一同删除，此时dp[i][j] = dp[i+1][j-1]
  2. 遍历所有可能的拆分点k（i ≤ k < j），将区间拆分为[i,k]和[k+1,j]两部分，取两部分最短结果的和的最小值，即dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

如果需要得到具体的最短字符串而非长度，只需要将dp[i][j]的存储内容从长度替换为对应区间的最短结果字符串即可。 #

Python 实现代码 #

def min_string_after_remove_palindromes(s: str) -> str:
    n = len(s)
    # dp[i][j] 存储s[i..j]删除所有回文子串后的最短字符串
    dp = [["" for _ in range(n)] for _ in range(n)]
    
    # 初始化长度为1的区间
    for i in range(n):
        dp[i][i] = s[i]
    
    # 遍历区间长度，从2到n
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            # 初始默认取原串作为初始值
            best = s[i:j+1]
            # 情况1：两端字符相等
            if s[i] == s[j]:
                if length == 2:
                    best = ""
                else:
                    candidate = dp[i+1][j-1]
                    if len(candidate) < len(best):
                        best = candidate
            # 情况2：遍历所有拆分点找更优解
            for k in range(i, j):
                candidate = dp[i][k] + dp[k+1][j]
                if len(candidate) < len(best):
                    best = candidate
            dp[i][j] = best
    return dp[0][n-1]

# 测试示例
print(min_string_after_remove_palindromes("lolahal")) # 输出: l

复杂度说明 #

• 时间复杂度：O(n³)，n为输入字符串长度，需要遍历所有区间，每个区间最多遍历n个拆分点
• 空间复杂度：O(n²)，用于存储dp矩阵

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