Chương trình tìm số ký tự tối thiểu bị xóa để biến chữ A thành chữ B trong Python

Giả sử chúng ta có một chuỗi s chỉ bao gồm hai chữ cái A và B, chúng ta phải tìm số lượng chữ cái tối thiểu cần phải xóa khỏi s để nhận được tất cả các lần xuất hiện của As trước tất cả các lần xuất hiện của B.

Vì vậy, nếu đầu vào là S ="AABAABB", thì đầu ra sẽ là 1, vì Chúng ta có thể loại bỏ chữ A cuối cùng để lấy AABBB

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• a_right:=số lần xuất hiện của "A" trong s

• b_left:=0

• ans:=a_right

• đối với mỗi chỉ mục i và ký tự c trong s, thực hiện

  • nếu c giống với "A" thì

    • a_right:=a_right - 1

  • nếu không,

    • b_left:=b_left + 1

  • ans:=tối thiểu ans và a_right + b_left

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

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))

Đầu vào

"AABAABB"

Đầu ra

1