BAsiC substring problem

区間 $[0,i)$ (0-indexed) の A , B , C の個数を、（逆元の存在する）何らかのデータ $cnt_i$ として表すことを考えます。

「$cnt_i = 0 \iff [0,i)$ に含まれる A , B , C の個数が等しい」が成り立つように $cnt_i$ を定めれば、 「$cnt_i = cnt_j \ (i < j) \iff [i,j)$ に含まれる A , B , C の個数が等しい」 が成り立ち、Zero-Sum Ranges の要領で条件を満たす部分文字列の個数を数えることが出来ます。

このような $cnt_i$ の一例としては、$[0,i)$ に含まれる A , B , C の個数をそれぞれ $a_i,b_i,c_i$ として、

• $(a_i-b_i,\ b_i-c_i)$ というペア
• $a_i + b_i \times 10^6 - c_i \times (10^6 + 1)$

などが挙げられます。あとはこれを $i=0,1,\dots,|s|$ について計算し、$cnt_i$ が同じものを2つ選ぶ場合の数を求めればよいです。

計算量は、連想配列を用いた場合 $O(|s| \ {\rm log} |s|)$ または $O(|s|)$ （ならし）となります。