Python - Chuỗi 1 dài nhất trong chuỗi nhị phân sau khi đảo tối đa 1 bit 0

Cho chuỗi nhị phân s. Cho phép đổi tối đa 1 ký tự '0' thành '1'. Tìm độ dài chuỗi con liên tiếp toàn '1' dài nhất.

Ví dụ

Input: s = "1010110001"
Output: 4
Giải thích: Đổi '0' tại chỉ số 3 → "1011110001", chuỗi '1' dài nhất là 4.

Thuật toán: Cửa sổ trượt (Sliding Window)

Duy trì cửa sổ [left, right] chứa tối đa 1 ký tự '0':

• ones: số lượng '1' trong cửa sổ
• Mở rộng right, cập nhật ones
• Nếu (right - left + 1) - ones > 1 (quá 1 số '0'): thu hẹp left, cập nhật ones
• Kết quả = max độ dài cửa sổ

Mã Python

def solve(s):
    n = len(s)
    ans = ones = left = right = 0
    while right < n:
        if s[right] == "1":
            ones += 1
        # Số '0' trong cửa sổ = độ dài - số '1'
        while right - left + 1 - ones > 1:
            if s[left] == "1":
                ones -= 1
            left += 1
        ans = max(ans, right - left + 1)
        right += 1
    return ans

# Test
s = "1010110001"
print(solve(s))  # Output: 4

Phân tích độ phức tạp

• Thời gian: O(n) - mỗi chỉ số vào/ra cửa sổ tối đa 1 lần
• Không gian: O(1)

Mở rộng

Nếu cho phép đổi k bit '0', chỉ cần thay điều kiện > 1 thành > k. Đây là bài toán kinh điển "Max Consecutive Ones III" (LeetCode 1004).