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"）。

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

  • 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

示例

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

Open Compiler
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"

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

2

更新于：2021年10月6日

492 次浏览

开启你的职业生涯

完成课程后获得认证

开始学习
广告