B: Reverse and Compare - AtCoder Grand Contest 019
文字列Aが与えられる。任意の添字i, jを選び、連続部分文字列A[i]..A[j]を反転させる。(i=jならなにもしないのと同値)。この操作を1回だけしたときに得られる文字列は何通りあるか?
左の文字から順に数えていく。今見ている文字がcのとき、そこより右の文字がすべてc以外なら右にある文字数だけ、反転したら別の文字列が構成できる。もし、cがk>0 個あるとき、その反転は両脇のcを除いた反転と同じなので、現時点ではカウントしないこととする。こうやって和をとっていけば全部の組み合わせがカウントできる。
アルファベットはa-zなので、これらの文字のカウントの累積和を作っておくことで、あるインデックスより左にある特定の文字、と言うものをO(1)でカウントできる。合わせて計算量はO(N)。