题解 | 小红的华撃串

n = int(input().strip())
s = input().strip()  # 长度为 n 的 01 串

INF = 10**9

# dp[k][b]：处理到当前位置时，发生了 k 次相邻变化，且当前位置字符为 b(0/1) 的最少翻转次数
dp = [[INF] * 2 for _ in range(4)]

# 初始化第 0 位
for b in (0, 1):
    dp[0][b] = 0 if int(s[0]) == b else 1

# 逐位转移
for i in range(1, n):
    x = int(s[i])
    ndp = [[INF] * 2 for _ in range(4)]
    for k in range(4):
        for pre in (0, 1):
            if dp[k][pre] == INF:
                continue
            for cur in (0, 1):
                nk = k + (1 if pre != cur else 0)
                if nk <= 3:
                    cost = dp[k][pre] + (0 if x == cur else 1)
                    if cost < ndp[nk][cur]:
                        ndp[nk][cur] = cost
    dp = ndp

ans = min(dp[3][0], dp[3][1])
print(ans)