\(\mathrm{DP}[n][L][x]=A_L A_{L+1}\ldots A_{L+3^n} \)に対して操作をした結果を\( x \)にするために必要な変更箇所の最小値

とすると、

\(\mathrm{DP}[n][L][x]=\begin{cases} 0 & n=0 かつ x=A_L\\ 1 & n=0 かつ x\neq A_L\\ DP[n-1][L][x], DP[n-1][L+3^{n-1}][x], DP[n-1][L+2\times 3^{n-1}][x] のうち小さい2つの和 & \text{otherwise} \end{cases}\)

となり、メモ化再帰などにより解くことができます。

N=int(input())
S=input()

def dfs(n,l):
  if n==0:
    return (0,1) if S[l]=="0" else (1,0)
  zero,one=zip(*[dfs(n-1,l+k*3**(n-1)) for k in range(3)])
  return (sum(zero)-max(zero),sum(one)-max(one))

print(max(dfs(N,0)))

なお、各 \(n,L\) について、\(DP[n][L][0],DP[n][L][1]\) は一方が 0 で他方が非0 になります。このため、DP[n][L] の表し方として、ここで述べた (0にする最小値, 1にする最小値) 以外にも、(値が0なのは0と1のどちらか, 他方の値) という持ち方も考えられ、公式解説 はこちらによるものです。