โปรแกรมนับจำนวนการดำเนินการเพื่อกำจัดบิตติดกัน 3 ตัวที่เหมือนกันใน Python

สมมติว่าเรามีสตริงไบนารี s พิจารณาการดำเนินการที่เลือกบิตหนึ่งและพลิกค่าจาก 0 เป็น 1 หรือ 1 เป็น 0 เราต้องหาจำนวนการดำเนินการขั้นต่ำเพื่อให้ได้สตริงที่ไม่มีบิตติดกัน 3 ตัวที่เหมือนกัน

เช่น ถ้าอินพุตคือ s = "10011100" ผลลัพธ์จะเป็น 1 เพราะสามารถพลิกบิตที่ดัชนี 4 จาก 1 เป็น 0 ได้ สตริงกลายเป็น "10010100" ซึ่งไม่มีบิตติดกัน 3 ตัวที่เหมือนกัน

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

1. กำหนด l := 0, count := 0
2. วนลูป while l < len(s):
   • r := l
   • วนลูป while r < len(s) and s[r] == s[l] ให้ r := r + 1
   • count := count + floor((r - l) / 3)
   • l := r
3. คืนค่า count

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

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

อินพุต

"10011100"

เอาต์พุต

1