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

示例

讓我們看看下面的實現，以便更好地理解：

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

更新於：2021年10月6日

492 次瀏覽

開啟你的職業生涯

完成課程後獲得認證

開始學習
廣告