寻找最小删除数以在 Python 中平衡字符串的程序

假设我们有一个字符串 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”)。

示例

让我们看看以下实现以获得更好的理解 -

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

猜你喜欢