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

สมมติว่าเรามีสตริงไบนารี เราต้องหาจำนวนการสลับ (swaps) น้อยที่สุดเพื่อให้ 1 ทั้งหมดอยู่ติดกันที่ตำแหน่งใดก็ได้ในสตริง

ตัวอย่าง: "10101001101" ผลลัพธ์คือ 3 (เป็นไปได้เป็น "00000111111")

ขั้นตอนการแก้ปัญหา (Sliding Window + Prefix Sum)

1. แปลงสตริงเป็น list ของ int (data)
2. นับจำนวน 1 ทั้งหมด one
3. สร้าง prefix sum array summ
4. Sliding window ขนาด one:
   • left = 0, right = one - 1
   • คำนวณจำนวน 1 ในหน้าต่างด้วย prefix sum
   • ans = min(ans, one - count_ones_in_window)
   • เลื่อนหน้าต่างขวา 1 ก้าว
5. คืนค่า ans

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

class Solution:
    def solve(self, data):
        data = list(map(int, list(data)))
        one = 0
        n = len(data)
        summ = [0] * n
        summ[0] = data[0]
        one += data[0]
        
        for i in range(1, n):
            summ[i] = summ[i-1] + data[i]
            one += data[i]
        
        ans = one
        left = 0
        right = one - 1
        
        while right < n:
            if left == 0:
                temp = summ[right]
            else:
                temp = summ[right] - summ[left-1]
            ans = min(ans, one - temp)
            right += 1
            left += 1
        
        return ans

ob = Solution()
print(ob.solve("10101001101"))  # Output: 3

อินพุต

"10101001101"

เอาต์พุต

3