Chương trình tìm số lần hoán vị tối thiểu để gom tất cả 1 lại với nhau trong Python

Cho chuỗi nhị phân, tìm số lần hoán vị (swap) tối thiểu để gom tất cả các '1' lại với nhau ở bất kỳ vị trí nào.

Ví dụ: "10101001101" → kết quả 3 (có thể biến thành "00000111111").

Giải thuật (Cửa sổ trượt + Prefix Sum)

1. Chuyển chuỗi thành mảng các số 0/1.
2. Đếm tổng số 1: .
3. Tính prefix sum .
4. Cửa sổ kích thước trượt qua mảng: tìm cửa sổ chứa nhiều 1 nhất.
5. Số swap = .

Ví dụ minh họa

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

Đầu vào

"10101001101"

Đầu ra

3