文字列 \(T\) が「よい文字列」である条件は、\(T\) に含まれる A, B, C の個数の偶奇がすべて一致することです。

続いて、ある文字列中の「よい文字列である連続する部分文字列」を数えることを考えます。文字列 \(S\) について、前から順に各文字の個数の累積和を計算しておくと、\(S\) の \(l\) 文字目から \(r\) 文字目がよい文字列である条件は、\(r\) 文字目までの累積和と \(l-1\) 文字目までの累積和の差が全ての文字について偶数であるか、または全ての文字について奇数であることです。

このことから、累積和については実際の個数ではなく、個数の偶奇のみが分かっていれば良いです。 また、例えば各文字の個数の累積和が（偶数、偶数、偶数）という状態と（奇数、奇数、奇数）という状態が合わせて \(s\) 回登場しているとすると、\(s(s-1)/2\) 個のよい文字列が取れます。他の状態についても同様です。

したがって、「A, B, C についての累積和の偶奇の状態ごとに、その状態が何度登場したか」で分類して文字列を数えられれば良いですが、このままでは状態が \(2^3=8\) 通りあります。しかし、偶奇が全て逆である組は同一視してよいので、例えば ( A の個数 - B の個数) と ( A の個数 - C の個数) についての偶奇を持っておけばよく、\(4\) 通りの状態についてそれぞれの出現回数を数えれば十分になります。（また、A, B, C に \(1, 2, 3\) を割り当てて累積 xor を考えることでも同様に状態を分類できます。）

さらに、長さ \(N\) の文字列について、全ての状態の現れる回数の和は \(N+1\) であるため、このうち \(3\) つだけ数えておけばよく、これらとその時点での状態を index に取って DP を行うことができます。具体的には、以下のような定義の DP テーブルを用います。計算量は \(O(N^4)\) です。

\(dp[i][x][a][b][c]\) \(=\) \(i\) 文字目まで見て、累積和の状態が \(x\) であり、ここまでに累積和の状態 \(1,2,3\) がそれぞれ \(a,b,c\) 回登場しているような文字列の数

ただし、累積和の偶奇の状態に適当に \(0,1,2,3\) の番号をつけておいています。

最後に、各状態の登場回数から「よい文字列」の数が求まるので、これが \(K\) 以上となっている文字列の数を足し合わせればよいです。

実装例：https://atcoder.jp/contests/arc188/submissions/60033005