Python程式：查詢刪除字元的最小數量以使A在B之前

假設我們有一個字串s，它僅包含兩個字母A和B，我們需要找到需要從s中刪除的字母的最小數量，以使所有A都出現在所有B之前。

因此，如果輸入類似於S = "AABAABB"，則輸出將為1，因為我們可以刪除最後一個A以得到AABBB

為了解決這個問題，我們將遵循以下步驟

• a_right := s中“A”出現的次數

• b_left := 0

• ans := a_right

• 對於每個索引i和字串s中的字元c，執行以下操作

  • 如果c與“A”相同，則

    • a_right := a_right - 1

  • 否則，

    • b_left := b_left + 1

  • ans := ans和a_right + b_left的最小值

• 返回ans

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

示例

 即時演示

class Solution:
   def solve(self, s):
      a_right = s.count("A")
      b_left = 0

      ans = a_right
      for i, c in enumerate(s):
         if c == "A":
            a_right -= 1
         else:
            b_left += 1
         ans = min(ans, a_right + b_left)
      return ans

ob = Solution()
S = "AABAABB"
print(ob.solve(S))

輸入

"AABAABB"

輸出

1

Arnab Chakraborty

更新於: 2020年11月10日

784 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習