与えられた文字列を \(S[1:N]\), \(S[N+1:2N]\), \(S[2N+1:3N]\) に三等分しましょう。次の条件が成り立つように、全ての文字を \(N\) 個の組 \((S_{a_i}, S_{b_i}, S_{c_i})\) に分けようとしてみます。

• $1 \le a_i \le N$
• $N+1 \le b_i \le 2N$
• $2N+1 \le c_i \le 3N$
• $S_{a_i}, S_{b_i}, S_{c_i}$ は A , B, C の並べ替えである。

これができれば、A, B, C の並べ替えそれぞれに対して部分列を用意し、その並べ替えとなっている組を全て入れることができます。すると、各部分列は明らかに良い文字列となります。

では、この分割はどのように行えばよいでしょうか。A B, C の並べ替えを一つずつ試していきます。現在 \((X, Y, Z)\) を試しているとすると、\(S[1:N]\) に \(X\) が \(1\) つ以上あり、\(S[N+1:2N]\) に \(Y\) が \(1\) つ以上あり、\(S[2N+1:3N]\) に \(Z\) が \(1\) つ以上ある限り、それらを取り出して対応する組を作ります。作れなくなったら終了します。

このようにして全ての文字を分けることができることを示します。\(K\) 個の組を作った時点で、\(S[1:N]\), \(S[N+1:2N]\), \(S[2N+1:3N]\) にそれぞれ \(N-K\) 文字が残り、その中に A, B, C がそれぞれ \(N-K\) 個ずつあります。ここで、次のような二部グラフを考えます。このグラフは左側の頂点として文字列 \(S[1:N]\), \(S[N+1:2N]\), \(S[2N+1:3N]\) を、右側の頂点として文字 A, B, C を持ち、文字列に文字 \(X\) が \(1\) 個以上残っているときにその文字列と \(X\) は辺で結ばれています。ホールの定理より、このグラフは完全マッチングを持ちます。なぜなら、文字列のうちどの \(m\) 個にも合計 \(m(N-K)\) 文字が含まれ、また各種類の文字は \((N-K)\) 個しか残っていないため、これらの \(m\) 個の文字列は少なくとも \(m\) 個の文字とマッチする必要があるからです。これは、A, B, C の並べ替え \((X, Y, Z)\) であって、\(X, Y, Z\) がそれぞれ第一、第二、第三の文字列に含まれるものが存在することを意味します。となると、この並べ替えを試したときにこの三文字は取り出されていたことになります。

計算量は \(O(N)\) です。

おまけ: 同様に \(5\) つの部分列に分割できますか？