最优子串去除算法问题

Question

问题如下：

给定一个仅由字符 X 和 Y 组成的字符串 input_str，您可以一步删除 XY 或 YY 子字符串。每次移动后，绳子的其余部分都会连接在一起。执行任意次数的移动后，找到剩余字符串的最小可能长度。

例如字符串“YXYYX”：

我们首先删除从索引 1 开始的“XY” -> YYX 然后我们删除“YY 从索引 0 开始 -> X

所以剩余字符串的最小可能长度是1。

我似乎想不出任何解决算法，因为显然移动/删除的顺序很重要。

如果有人能提供帮助，我将不胜感激。

我尝试在 leetcode 上查看类似的子字符串删除问题，但我找不到任何足够相关的内容来解决这个问题。

Answer 1

您可以实现如下所示的递归函数，将极小极大算法应用于特定问题。此实现检查输入字符串 's' 中是否存在 'XY' 和 'YY'，并递归地删除每个步骤中第一次出现的 'XY' 或 'YY'，返回删除所有出现的 'XY' 或 'YY' 所需的最小长度这些图案。但是，正如您所指出的，由于其指数时间复杂度，该解决方案的性能对于更复杂的规则可能不是最佳的。

def minimax(s):
    if 'XY' not in s and 'YY' not in s:
        return len(s)
    elif 'XY' in s and 'YY' not in s:
        return minimax(s.replace('XY', '', 1))
    elif 'XY' not in s and 'YY' in s:
        return minimax(s.replace('YY', '', 1))
    else:
        return min(minimax(s.replace('XY', '', 1)), minimax(s.replace('YY', '', 1)))