文字列の先頭 \(i\) 文字における B の個数から A の個数を引いたものを \(f_{AB}(i)\) と定義し、\(M_A = max(f_{AB}(0), f_{AB}(1), \ldots, f_{AB}(3N))\) とします。同様に \(f_{BC}, f_{CA}\) を定義し、\(M_B = max(f_{BC}(0), f_{BC}(1), \ldots, f_{BC}(3N))\), \(M_C = max(f_{CA}(0), f_{CA}(1), \ldots, f_{CA}(3N))\) とします。

文字列 \(T\) が題意を満たす \(N\) 個の部分列に分割可能である必要十分条件が \(M_A+M_B+M_C\le N\) であることを証明します。

必要性: そのような分割方法が存在するなら、\(M_A+M_B+M_C\le N\) である。

文字列を \(A_1\) 個の ABC という部分列、\(B_1\) 個の BCA という部分列、\(C_1\) 個の CAB という部分列に分割できたとします。すると、差引個数 \(M_A\) が \(B_1\) を超えることはありません。なぜなら、部分列 ABC, CAB では A が B より前にあるからです。同様に、差引個数 \(M_B\) が \(C_1\) を、\(M_C\) が \(A_1\) を超えることはないため、\(M_A+M_B+M_C\le A_1 + B_1 + C_1 = N\) となります。

十分性: \(M_A+M_B+M_C\le N\) であるなら、\(3N\) 個の文字を (\(i\) 個目の A, \((i+M_A)\) 個目の B, \((i+M_A+M_B)\) 個目の C) という組に分割可能である（ここで番号付けは循環し、文字 \(X\) について \(i+N\) 個目の \(X\) は \(i\) 個目の \(X\) を指す）。

文字列 \(S+S+S\) を考えます。この文字列で、任意の \(i\le 2N\) について、\(i\) 個目の A が \(i+M_A\) 個目の B より前にあり、\(i\) 個目の B が \(i+M_B\) 個目の C より前にあり、\(i\) 個目の C が \(i+M_C\) 個目の A より前にあることに注意します（差引個数に関する議論より）。従って、\(i\) 個目の A は \(i+M_A\) 個目の B より前にあり、この \(i+M_A\) 個目の B は \(i+M_A+M_B\) 個目の C より前にあり、 この \(i+M_A+M_B\) 個目の C は \(i+M_A+M_B+M_C\) 個目の A より前にあり、この \(i+M_A+M_B+M_C\) 個目の A は \(i+N\) 個目の A と一致するかそれより前にあります。これは明らかに \(i\) 個目の A、\((i+M_A)\) 個目の B、 \((i+M_A+M_B)\) 個目の C が「正しい」順で循環していることを意味するため、この割り当ては成立します。

この観察を用いて、簡単に \(O(N^6)\) の DP を書くことができます。単にこれまでに採用した A, B, C の個数と \(f_{AB}(i), f_{BC}(i), f_{CA}(i)\) の暫定最大値を記録するだけです。一見するとこれは \(O(N^7)\) ですが、\(i\) 文字目を処理した時点での合計文字数が \(i\) でなければならないため、定数倍のとても小さい \(O(N^6)\) となります（\(N\le 40\) であったとしても問題ありません）。

おまけ: A, B, C, D を\(N\) 個ずつ含む文字列を ABCD, BCDA, CDAB, DABC に分割する問題であったらどうでしょう？