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

更新于: 2020年11月10日

784 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告