Chương trình tìm số ký tự xóa tối thiểu để A đứng trước B trong Python

Cho chuỗi s chỉ chứa 'A' và 'B'. Tìm số ký tự cần xóa tối thiểu để tất cả 'A' đứng trước tất cả 'B'.

Ví dụ

s = "AABAABB"

Xóa 'A' cuối cùng (vị trí 4) → "AABBBB" → kết quả: 1.

Thuật toán (Prefix/Suffix Count)

1. a_right = tổng số 'A' trong chuỗi.
2. b_left = 0.
3. ans = a_right (xóa tất cả A).
4. Duyệt chuỗi từ trái sang phải:
   • Nếu 'A': a_right--.
   • Nếu 'B': b_left++.
   • ans = min(ans, a_right + b_left).
5. Trả về ans.

Ý tưởng: tại mỗi vị trí phân chia, xóa A bên phải + B bên trái.

Triển khai Python

class Solution:
    def solve(self, s):
        a_right = s.count('A')
        b_left = 0
        ans = a_right
        
        for ch in s:
            if ch == 'A':
                a_right -= 1
            else:  # 'B'
                b_left += 1
            ans = min(ans, a_right + b_left)
        
        return ans

# Test
ob = Solution()
print(ob.solve("AABAABB"))  # 1
print(ob.solve("BBBB"))     # 0
print(ob.solve("AAAA"))     # 0
print(ob.solve("BBAA"))     # 2

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(1).