Đếm số phép toán tối thiểu để xóa ba bit giống nhau liên tiếp trong Python

Cho một chuỗi nhị phân s. Một phép toán cho phép chọn một bit và đảo giá trị của nó (0 thành 1 hoặc 1 thành 0). Tìm số phép toán tối thiểu để chuỗi không còn chứa ba bit giống nhau liên tiếp.

Ví dụ: s = "10011100" → kết quả 1 (đảo bit tại chỉ số 4 từ 1 thành 0, chuỗi thành "10010100").

Thuật toán

1. Khởi tạo l = 0, count = 0.
2. Trong khi l < len(s):
   • Đặt r = l.
   • Mở rộng r khi r < len(s) và s[r] == s[l] (tìm đoạn liên tiếp cùng ký tự).
   • Cộng vào count giá trị (r - l) // 3 (mỗi 3 bit liên tiếp cần 1 phép đảo).
   • Cập nhật l = r.
3. Trả về count.

Mã Python

def solve(s):
    l = 0
    count = 0
    while l < len(s):
        r = l
        while r < len(s) and s[r] == s[l]:
            r += 1
        count += (r - l) // 3
        l = r
    return count

s = "10011100"
print(solve(s))  # 1

Đầu vào / Đầu ra

Input: "10011100"

Output: 1