原案:vwxyz

部分文字列に含まれる A,B,C の個数をそれぞれ \(A,B,C\) とします。

条件 \(X\) を満たすような部分文字列の個数を \(f(X)\) と表すことにします。

包除原理より、求める答えは
\(\frac{N(N+1)}{2}-f(A=B)-f(A=C)-f(B=C)+3f(A=B=C)-f(A=B=C)\\ =\frac{N(N+1)}{2}-f(A=B)-f(A=C)-f(B=C)+2 f(A=B=C)\)
と変形できます。

\(f(A=B=C)\) の求め方を書きます（それ以外も同様に求めることができます）。

\(S\) の先頭から \(i(0 \leq i \leq N)\) 文字に含まれる A,B,C の個数をそれぞれ \(A_i,B_i,C_i\) と表すことにすると、\(S\) の \(l+1\) 文字目から \(r\) 文字目まで(\(0 \leq l \lt r \leq N\))に含まれる A,B,C の個数はそれぞれ \(A_r-A_l,B_r-B_l,C_r-C_l\) です。
\(A_r-A_l=B_r-B_l=C_r-C_l\) は \((A_l-B_l,A_l-C_l)=(A_r-B_r,A_r-C_r)\) と同値なので、各 \(i\) について \((A_i-B_i,A_i-C_i)\) を求め、これが等しいような \(l,r\) のペアの個数を求めればよいです。
\((A_i-B_i,A_i-C_i)\) の出現回数を連想配列などで管理します。
同じペアが \(c\) 回出現するとき、その中から \(l,r\) を選ぶ方法は \(\frac{c(c-1)}{2}\) 通りあり、これを足し合わせていくことで \(f(A=B=C)\) を \(O(N)\) や \(O(N\log N)\) で計算することができます。

同様に \(f(A=B),f(A=C),f(B=C)\) も求めることができ、答えを求めることができます。