Chương trình tìm số 1 liên tiếp dài nhất sau khi hoán vị một cặp bit trong Python

Mô tả bài toán

Cho chuỗi nhị phân s. Có thể hoán vị tối đa một cặp ký tự. Tìm độ dài chuỗi con toàn 1 dài nhất sau hoán vị.

Ví dụ: s = "1111011111" → đầu ra 9 (hoán vị s[4] và s[9] để có 9 số 1 liên tiếp).

Giải thuật (Cửa sổ trượt cho phép tối đa 1 số 0)

1. Khởi tạo l = 0, cnt = 0 (số 0 trong cửa sổ), ans = 0.
2. Duyệt r từ 0 đến len(s)-1:
   • cnt += (s[r] == "0").
   • Nếu cnt > 1: cnt -= (s[l] == "0"), l += 1.
   • ans = max(ans, r - l + 1).
3. Trả về min(ans, s.count("1")) (không thể vượt quá tổng số 1).

Ví dụ mã Python

class Solution:
    def solve(self, s):
        l = 0
        cnt = 0
        ans = 0
        for r in range(len(s)):
            cnt += s[r] == "0"
            if cnt > 1:
                cnt -= s[l] == "0"
                l += 1
            ans = max(ans, r - l + 1)
        return min(ans, s.count("1"))

ob = Solution()
s = "1111011111"
print(ob.solve(s))

Đầu vào

"1111011111"

Đầu ra

9