从两端或中间删除字符构造全'A'字符串的最小成本求解问题

问题描述 #

给定一个仅由'A'和'B'组成的字符串，可执行两类删除操作：

1. 删除字符串任意一端的字符，成本为1
2. 删除字符串中间任意位置的字符，成本为2
   求将原字符串转换为仅含'A'的字符串所需的最小操作成本。

示例 #

输入字符串为"BBABAA"时，最小删除成本为4：先删除左侧2个'B'（成本2），再删除右侧唯一的'B'（成本2），总成本为4。

现有实现 #

带缓存自顶向下动态规划解法如下：

def MRC_helper(s, count, cache):
    if count == 0:
        cache[s] = 0
        cache[s[::-1]] = 0
        return 0
    if s in cache:
        return cache[s]

    min_cost = len(s)
    for i in range(len(s)):
        new_count = count - int(s[i] == 'B')
        new_s = s[:i]+s[i+1:]
        if i == 0 or i == len(s)-1:
            min_cost = min(min_cost, 1 + MRC_helper(new_s, new_count, cache))
        elif s[i] == 'B':
            min_cost = min(min_cost, 2 + MRC_helper(new_s, new_count, cache))

    cache[s] = min_cost
    cache[s[::-1]] = min_cost
    return min_cost

def minRemovalCost(s):
    min_cost = MRC_helper(s, s.count('B'), {})
    return min_cost

疑问 #

思路是遍历所有可删除字符，计算删除后子串的转换成本，取最小值缓存，同时缓存正逆序字符串的结果。朋友说可以用贪心求解，不认可，请问是否有更优的解法？ #

你提供的动态规划解法逻辑正确，但时间复杂度较高，最坏情况达到O(n³)，仅适合短字符串场景。
确实存在更优的O(n)时间复杂度解法，同时你朋友提到的贪心思路也是成立的：

核心逻辑推导 #

最终保留的全'A'序列，对应原字符串中必然存在左右两个边界left和right：所有保留的'A'都在[left, right]区间内，区间外的所有字符全部从两端删除（成本1/个），区间内的所有'B'只能从中间删除（成本2/个）。
总成本公式可推导为：
总成本 = left + (n-1-right) + 2 * 区间[left, right]内B的数量
我们可以通过前缀B计数+维护最小值的方式，把这个公式的计算优化到线性时间：

1. 预处理前缀B计数数组pre_b，pre_b[i]表示前i个字符中'B'的数量
2. 把总成本公式变形为：(left - 2*pre_b[left]) + (2*pre_b[right+1] - right) + (n-1)
3. 遍历右边界right的同时，维护左边界left<=right的最小left - 2*pre_b[left]值，即可快速得到当前右边界对应的最小成本

优化后代码实现 #

def minRemovalCost(s):
    n = len(s)
    if n == 0:
        return 0
    # 预处理前缀B计数
    pre_b = [0]*(n+1)
    for i in range(n):
        pre_b[i+1] = pre_b[i] + (1 if s[i] == 'B' else 0)
    # 边界情况：全删的成本是n
    min_cost = n
    min_left_val = 0 # 初始left=0时的值
    for right in range(n):
        if s[right] == 'A':
            # 仅当右边界是A时才有计算意义
            current_cost = min_left_val + (2 * pre_b[right+1] - right) + (n-1)
            min_cost = min(min_cost, current_cost)
        # 更新最小左边界值，left可以到right+1的位置
        current_left_val = (right+1) - 2 * pre_b[right+1]
        if current_left_val < min_left_val:
            min_left_val = current_left_val
    return min_cost

关于贪心思路的说明 #

贪心思路是成立的：因为中间删除B的成本是两端删除的2倍，所以优先删除两端的B，当剩下的B都在中间区域时，只需要比较「删除中间所有B的总成本」和「删除中间B所在区域一侧所有字符的总成本」，取更小值即可，和上面推导的最优解结果完全一致。 #

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