Original proposer: vwxyz

Let \(A\), \(B\), and \(C\) denote the number of occurrences of A, B, and C in a substring, respectively.

Let \(f(X)\) denote the number of substrings satisfying condition \(X\).

By Inclusion-Exclusion Principle, the sought answer equals
\(\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).\)

We describe how to find \(f(A=B=C)\). (The other values can also be found likewise.)

Let \(A_i\), \(B_i\), and \(C_i\) respectively be the number of occurrences of A, B, and C within the first \(i(0 \leq i \leq N)\) characters of \(S\). Then the numbers of occurrences of A, B, and C within the substring from the \((l+1)\)-th through the \(r\)-th characters of \(S\) are \(A_r-A_l\), \(B_r-B_l\), and \(C_r-C_l\), respectively.
Since \(A_r-A_l=B_r-B_l=C_r-C_l\) is equivalent to \((A_l-B_l,A_l-C_l)=(A_r-B_r,A_r-C_r)\), we may find \((A_i-B_i,A_i-C_i)\) for each \(i\), and count the number of pairs \((l,r)\) that yields the same value for this pair.
Manage the frequencies of \((A_i-B_i,A_i-C_i)\) in a data structure like an associative array.
If a certain pair occurs \(c\) times, there are \(\frac{c(c-1)}{2}\) ways to choose \(l\) and \(r\) from them. By summing them up, \(f(A=B=C)\) can be found in a total of \(O(N)\) or \(O(N\log N)\) time.

\(f(A=B)\), \(f(A=C)\), and \(f(B=C)\) can be found likewise, so the answer can be computed.