人 \(1\) が投票するタイミングとして考えられるものは \(N\) 個ありますが、そのうちタイミングが早い順から投票 \(1,2,\dots,N\) と呼ぶこととします。ここで、投票 \(i,i+1\) の結果が異なるならば \(i+1 \le j\) に対して投票 \(i,j\) の結果が異なることが分かります。(投票 \(i,i+1\) の結果で異なる可能性があるのは \(i\) 文字目のみであり、ここが異なるならば投票 \(i,j\) の \(i\) 文字目も明らかに異なります。(★))

さて、ここからある投票結果になる \(i\) は区間になることが分かります。よって、投票 \(i,i+1(1 \le i \le N-1)\) であって異なるものの個数 \(+1\) が答えとなります。(★) に注意すると、人 \(2,3,\dots,N\) について累積和を計算しておくことでこれらは各 \(\mathrm{O}(1)\) で判定出来ます。よってこの問題を \(\mathrm{O}(N)\) で解くことが出来ます。

実装例(C++):https://atcoder.jp/contests/arc172/submissions/50419791