文字列 \(S\) の先頭から \(i\) 文字（\(0 \le i \le N\)）に含まれる
A, B, C の個数をそれぞれ \(A_i, B_i, C_i\) とします。

さらに、次のように差分を定義します。

\[ x_i := B_i - A_i,\quad y_i := C_i - A_i \]

区間 \((i, j]\)（すなわち \(i+1\) 文字目から \(j\) 文字目）の部分文字列を考えます。

この部分文字列における各文字の出現回数は、

\[ A_j - A_i,\; B_j - B_i,\; C_j - C_i \]

です。

これらが すべて異なる ための条件は、以下の3つです。

• \(A\) と \(B\) が異なる
  \( B_j - B_i \ne A_j - A_i \;\Longleftrightarrow\; x_j \ne x_i \)

• \(A\) と \(C\) が異なる
  \( C_j - C_i \ne A_j - A_i \;\Longleftrightarrow\; y_j \ne y_i \)

• \(B\) と \(C\) が異なる
  \( B_j - B_i \ne C_j - C_i \;\Longleftrightarrow\; x_j - x_i \ne y_j - y_i \)

最後の条件は変形して

\[ y_j - x_j \ne y_i - x_i \]

と書けます。

ここで重要な観察として、

\(x_i \ne x_j\) のもとでは
\(y_i = y_j\) と \(y_i - x_i = y_j - x_j\) が同時に成立することはない

という点があります。

したがって、 \(x_i\) ごとにグループ化し、その中で

• \(y_i\) の一致数
• \(y_i - x_i\) の一致数

を数えることで、重複を気にせずそれぞれ独立に引いてよいです。

実装例 (C++)