Python中查找使字符串平衡的最小删除次数的程序

假设我们有一个字符串s，只包含两个字符’s’和’t’。我们可以删除s中任意数量的字符以使字符串平衡。当不存在一对索引（i，j）满足i

因此，如果输入是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))

输入

"sststtst"

输出

2