โปรแกรมหา 1s ติดกันมากสุดหลังสลับคู่บิตเดียวใน Python

สมมติว่ามีสตริงไบนารี s สามารถสลับคู่ตัวอักษรได้สูงสุด 1 คู่ ต้องการหาความยาว substring 1s ติดกันมากสุดหลังสลับ

ตัวอย่าง: s = "1111011111" ผลลัพธ์ 9 สลับ s[4] กับ s[9] ได้ 9 ตัว 1 ติดกัน

ขั้นตอนการแก้ปัญหา

1. l = 0, cnt = 0, ans = 0
2. วน r จาก 0 ถึง len(s)-1:
   • cnt += (s[r] == "0")
   • ถ้า cnt > 1:
     • cnt -= (s[l] == "0")
     • l += 1
   • ans = max(ans, r - l + 1)
3. คืน min(ans, s.count("1")) (ไม่สามารถเกินจำนวน 1 ทั้งหมด)

ตัวอย่างโค้ด

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))

อินพุต

"1111011111"

เอาต์พุต

9