Python - หาสับสตริง 1 ติดกันยาวที่สุดหลังพลิก 0 ได้ 1 ครั้ง

โจทย์: กำหนดสตริงไบนารี s อนุญาตให้พลิก 0 เป็น 1 ได้สูงสุด 1 ครั้ง หาความยาวของสับสตริง (Contiguous Substring) ที่เป็น 1 ทั้งหมดยาวที่สุด

ตัวอย่าง

Input: s = "1010110001"
Output: 4
เหตุผล: พลิก 0 ตัวที่ index 3 ได้ "1011110001" สับสตริง 1 ติดกันยาวสุด = 4 (1111)

อัลกอริทึม: Sliding Window (Two Pointers)

รักษาหน้าต่างที่มี 0 สูงสุด 1 ตัว โดยใช้ left, right และนับจำนวน 1 (ones)

ขั้นตอนการทำงาน

left = right = 0, ones = 0, ans = 0
ขยาย right ไปทางขวา:
- หาก s[right] == '1' → ones++
ขณะที่ (right - left + 1) - ones > 1 (มี 0 มากกว่า 1 ตัว):
- ย่อหน้าต่างซ้าย: หาก s[left] == '1' → ones--
- left++
อัปเดต ans = max(ans, right - left + 1)
right++ และทำซ้ำ

โค้ด Python

def solve(s):
    n = len(s)
    ans = ones = left = right = 0
    
    while right < n:
        if s[right] == "1":
            ones += 1
        
        # หน้าต่างมี 0 มากกว่า 1 ตัว → ย่อซ้าย
        while right - left + 1 - ones > 1:
            remove = s[left]
            if remove == "1":
                ones -= 1
            left += 1
        
        ans = max(ans, right - left + 1)
        right += 1
    
    return ans

# ทดสอบ
s = "1010110001"
print(solve(s))  # Output: 4

การทำงานทีละขั้นตอน (Trace)

s = "1 0 1 0 1 1 0 0 0 1"

right	char	ones	window	zeros	left	ans
0	1	1	[0:0]	0	0	1
1	0	1	[0:1]	1	0	2
2	1	2	[0:2]	1	0	3
3	0	2	[0:3]	2	1	3
4	1	3	[1:4]	1	1	4
5	1	4	[1:5]	1	1	4
6	0	4	[1:6]	2	2	4
7	0	4	[2:7]	2	3	4
8	0	4	[3:8]	2	4	4
9	1	5	[4:9]	1	4	4

ความซับซ้อน

Time Complexity: O(n) - แต่ละตัวอักษรถูกเพิ่ม/ลบจากหน้าต่างสูงสุด 1 ครั้ง
Space Complexity: O(1)

การขยาย: พลิกได้ k ครั้ง

def solve_k_flips(s, k):
    n = len(s)
    ans = ones = left = 0
    for right in range(n):
        if s[right] == "1":
            ones += 1
        while right - left + 1 - ones > k:
            if s[left] == "1":
                ones -= 1
            left += 1
        ans = max(ans, right - left + 1)
    return ans