xxxx00000

$0$以上$N$以下の全ての$i$について，$i$文字目以前の文字を全て英小文字にし，$i+1$文字目以降の文字を全て数字にするために必要な操作回数を求め，その最小値を求めればよいです．

愚直な実装では$\mathrm{O}(N^2)$かかりますが，累積和を利用することで高速に求めることができます．

まず，$0$以上$N$以下の全ての$i$について，以下を求めます．

• $i$文字目までに含まれる数字の個数$A_i$

これは$\mathrm{O}(N)$で求まります．

この配列$A$をあらかじめ用意しておくことで，「$i$文字目以前の文字を全て英小文字にし，$i+1$文字目以降の文字を全て数字にするために必要な操作回数」は，以下の式で$\mathrm{O}(1)$で求めることができます．

$A_i + ((N - i) - (A_N - A_i)) = N - i - A_N + 2A_i$

よって，これを$0$以上$N$以下の全ての$i$について求め，その最小値を求めればよいので，全体で$\mathrm{O}(N)$で答えを求めることができます．