Python中的删除子串计算最大分数的程序

假设我们有一个字符串s和两个值x和y。我们可以执行给定的两种类型的操作任意次数。

搜索子字符串“ab”，如果存在，则通过删除它可以获得x分。
搜索子字符串“ba”，如果存在，则通过删除它可以获得y分。

我们必须在s上应用上述操作后找到我们可以获得的最大分数。

因此，如果输入为s =“cbbaacdeabb” x = 4 y = 5，则输出将为14，因为初始字符串为“cbbaacdeabb”，然后删除“cbbaacde（ab）b”以获得4，现在字符串为“cbbaacdeb”，然后删除“cb（ba）acdeb”获得更多的5，因此当前得分为4 + 5 = 9，现在字符串为“cbacdeb”，然后再次删除“c（ba）cdeb”，以获得额外的5，所以当前得分9 + 5 = 14，字符串现在为“ccdeb”，现在没有可以继续删除的内容。

要解决这个问题，我们将采用以下步骤：

a：=’a’，b:= ‘b’
ans：= 0，a_st：= 0，b_st：= 0
如果y > x，则
- 交换a和b
- 交换x和y
对于字符串s中的每个c，都要执行以下操作
- 如果c与a相同，则
  - a_st：= a_st + 1
- 否则，当c与b相同时，则
  - 如果a_st不为零，则
  - ans：= ans + x
  - a_st：= a_st – 1
  - 否则，则
  - b_st + = 1
- 否则，则
  - ans：= ans + y * a_st和b_st的最小值
  - a_st：= 0
  - b_st：= 0
返回ans + y * a_st和b_st的最小值

示例

让我们看一下下面的实现，以便更好地理解

def solve(s, x, y):
    a = 'a'
    b = 'b'
    ans = 0
    a_st = 0
    b_st = 0
    if y > x:
        a,b = b,a
        x,y = y,x
    for c in s:
        if c == a:
            a_st += 1
        elif c == b:
            if a_st:
                ans += x
                a_st -= 1
            else: b_st += 1
        else:
            ans += y * min(a_st, b_st)
            a_st = 0
            b_st = 0
    return ans + y * min(a_st, b_st)

s = "cbbaacdeabb"
x = 4
y = 5
print(solve(s, x, y))