用 Python 编写程序，查找使字符串平衡的最小删除次数

pythonserver side programmingprogramming更新于 2025/11/30 12:28:17

假设我们有一个字符串 s，其中只有两个字符"s"和"t"。我们可以删除 s 中的任意数量的字符，以使字符串平衡。我们可以说，当没有索引对 (i,j) 使得 i < j 且 s[i] = "t" 和 s[j]= "s" 时，s 是平衡的。我们必须找到使 s 平衡所需的最小删除次数。

因此，如果输入为 s = "sststtst"，则输出将为 2，因为我们可以删除索引 2 和 6 处的字符("sststtst" 改为 "sssttt")，或者删除索引 3 和 6 处的字符("sststtst" 改为 "sstttt")。

为了解决这个问题，我们将遵循以下步骤 −

cum_b := 0
count_a := 字符"s"的数量在 s 中
ans := 无穷大
对于 s 中的每个 x，执行
- 如果 x 与"s"相同，则
  - count_a := count_a - 1
  - ans := ans 和 (cum_b + count_a) 的最小值
- 否则，
  - cum_b := cum_b + 1
  - ans := ans 和 (cum_b-1 + count_a) 的最小值
返回 ans

示例

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

def solve(s):
   cum_b = 0
   count_a = s.count("s")
   ans = float("inf")
   for x in s:
      if x == "s":
         count_a-=1
         ans = min(ans,cum_b + count_a)
      else:
         cum_b+=1
         ans = min(ans,cum_b-1 + count_a)
   return ans

s = "sststtst"
print(solve(s))