Chương trình tìm số lần thay đổi tối thiểu cho chuỗi nhị phân xen kẽ trong Python

Giả sử ta có chuỗi nhị phân s. Xét phép toán lật một bit. Chuỗi s gọi là chuỗi xen kẽ (alternating) nếu không có hai ký tự liền kề nào giống nhau. Ta phải tìm số phép toán tối thiểu để làm cho s trở thành chuỗi xen kẽ.

Ví dụ: s = "11100011", kết quả là 3 vì nếu lật bit tại vị trí 1, 4, 7 thì thành "10101010" - tất cả đều xen kẽ.

Giải thuật

1. change := 0
2. even_1 := 0, even_0 := 0
3. odd_1 := 0, odd_0 := 0
4. For i từ 0 đến len(s) - 1:
   • Nếu i chẵn:
     • Nếu s[i] == '1': even_1++
     • Ngược lại: even_0++
   • Ngược lại (i lẻ):
     • Nếu s[i] == '1': odd_1++
     • Ngược lại: odd_0++
5. Nếu (even_1 + odd_0) > (even_0 + odd_1): change := even_0 + odd_1
6. Ngược lại: change := even_1 + odd_0
7. Trả về change

Ví dụ (Python)

def solve(s):
    change = 0
    even_1 = even_0 = 0
    odd_1 = odd_0 = 0
    for i in range(len(s)):
        if i % 2 == 0:
            if s[i] == '1':
                even_1 += 1
            else:
                even_0 += 1
        else:
            if s[i] == '1':
                odd_1 += 1
            else:
                odd_0 += 1
    if (even_1 + odd_0) > (even_0 + odd_1):
        change = even_0 + odd_1
    else:
        change = even_1 + odd_0
    return change

s = "11100011"
print(solve(s))

Input

"11100011"

Output

3