Chương trình tìm số lần lật bit nhỏ nhất để chuỗi nhị phân xen kẽ trong Python

Cho chuỗi nhị phân s. Có thể lấy một tiền tố và chuyển về cuối chuỗi. Tìm số bit cần lật tối thiểu để chuỗi không có 2 ký tự liên tiếp giống nhau (xen kẽ 0101... hoặc 1010...).

Ví dụ: s = "10010101111" → 2 (chuyển tiền tố "10" về cuối, lật 2 bit).

Giải thuật (Cửa sổ trượt trên chuỗi gấp đôi)

Xét chuỗi S+S độ dài 2N. Với mỗi vị trí i, tính sai số so với pattern xen kẽ bắt đầu từ 0 hoặc 1. Dùng cửa sổ trượt kích thước N để tìm min số lần lật.

• s += int(S[i%N]) ^ (i & 1): sai số so với pattern bắt đầu bằng 0.
• Khi cửa sổ đủ kích thước N: ans = min(ans, s, N-s) (N-s là sai số pattern bắt đầu bằng 1).
• Trượt cửa sổ: trừ sai số của phần tử rời khỏi cửa sổ.

Ví dụ minh họa

class Solution:
    def solve(self, S):
        N = len(S)
        ans = N
        s = 0
        for i in range(2 * N):
            s += int(S[i % N]) ^ (i & 1)
            if i >= N - 1:
                ans = min(ans, s, N - s)
                s -= int(S[(i - (N - 1)) % N]) ^ ((i - (N - 1)) & 1)
        return ans

ob = Solution()
s = "10010101111"
print(ob.solve(s))  # Output: 2

Đầu vào / Đầu ra

Input: "10010101111"

Output: 2