\(N=|S|\) とし、 \(dp_{i,j}\) を \(i\) 文字目までで作れる部分文字列のうち ABC の \(j\) 文字目まででと一致するものの個数とします。なお ? はどの文字にも割り当てられるとします。

これを \(0 \leq i \leq N,0 \leq j \leq 3\) で定義するとして求めたいものは \(dp_{N,3}\) です。

例えば \(i\) 文字目が A だったとしましょう。部分文字列が空文字列の場合にはこれを選ぶことで A を作れますが A と AB と ABC の場合には選択してはいけません。これをもとに \(dp_{i-1,j}\) から \(dp_{i,j}\) への遷移を考えられ、他の文字の場合にも同様です。

よって \(O \left( N \right)\) で解くことができます。「文字列の部分文字列が〇〇となるのは何通りか」というタイプの問題で、長さの制約がとても大きいかつ同じ文字が連続していたりする際は遷移が行列の形で書けることを利用して行列累乗というテクニックを使って解くことがあります。