โปรแกรมหาจำนวนการพลิกน้อยที่สุดเพื่อให้ค่าสลับกันในสตริงไบนารี Python

ได้รับสตริงไบนารี s อนุญาตให้ ย้าย prefix ไปท้ายสตริง (rotation) แล้วจึง พลิกบิต (0↔1) หาจำนวนการพลิกน้อยที่สุดเพื่อให้ไม่มีบิตติดกัน 2 ตัวเหมือนกัน (คือ 010101... หรือ 101010...)

ตัวอย่าง

Input: "10010101111"

Output: 2

ย้าย prefix "10" → "01010111110" พลิกบิตที่ 3 และ 5 จากขวา → "01010101010"

แนวทางแก้ปัญหา

Sliding Window บนสตริงยาว 2N (จัดการ rotation):

• พิจารณา 2 pattern เป้าหมาย: 0101... และ 1010...
• สำหรับแต่ละตำแหน่งเริ่มต้น rotation คำนวณจำนวน mismatch กับ pattern
• ใช้ sliding window ขนาด N บนสตริง s + s คำนวณ mismatch แบบ O(1) ต่อขั้น
• คำตอบ = min(mismatch, N - mismatch) ทุก window

การใช้งาน (Python)

class Solution:
    def solve(self, S):
        N = len(S)
        ans = N
        s = 0  # mismatch count สำหรับ pattern เริ่ม 0 (0101...)
        
        for i in range(2 * N):
            # เปรียบเทียบ S[i%N] กับ pattern ที่คาดหวัง (i&1 คือ 0,1,0,1...)
            s += (int(S[i % N]) ^ (i & 1))
            
            if i >= N - 1:
                # window size N พร้อม
                ans = min(ans, s, N - s)
                # ลบตัวออกจาก window ซ้าย
                left_idx = i - (N - 1)
                s -= (int(S[left_idx % N]) ^ (left_idx & 1))
        
        return ans

# ทดสอบ
ob = Solution()
print(ob.solve("10010101111"))  # Output: 2

ความซับซ้อน

• Time Complexity: O(N)
• Space Complexity: O(1)

อัลกอริทึมฉลาด ใช้ XOR และ sliding window หลีกเลี่ยงการสร้างสตริงใหม่