Let’s split our string into three equal parts: \(S[1:N]\), \(S[N+1:2N]\), \(S[2N+1:3N]\). We will try to split all characters into \(n\) triples \((S_{a_i}, S_{b_i}, S_{c_i})\), so that

• $1 \le a_i \le N$
• $N+1 \le b_i \le 2N$
• $2N+1 \le c_i \le 3N$
• Letters $S_{a_i}, S_{b_i}, S_{c_i}$ form a permutation of A , B, C.

If we can do this, we can have a separate subsequence for each permutation of A B, C, and add to it all triples forming corresponding permutation. Clearly, each subsequence will be a good string.

So, how do we split all characters into such triples? Try each permutation of A B, C one by one, say now we are trying \((X, Y, Z)\). While there is at least one \(X\) remaining in \(S[1:N]\), at least one \(Y\) remaining in \(S[N+1:2N]\), at least one \(Z\) remaining in \(S[2N+1:3N]\), take them and form a corresponding triple, end when you can’t.

Now let’s show that all characters will be split this way. Indeed, after forming \(K\) triples there are \(N-K\) characters left in each of \(S[1:N]\), \(S[N+1:2N]\), \(S[2N+1:3N]\), and there are exactly \(N-K\) left of each of A, B, C. Consider a bipartite graph with strings \(S[1:N]\), \(S[N+1:2N]\), \(S[2N+1:3N]\) as nodes of the left part, and characters A, B, C as nodes of the right, and connect string with character \(X\) with an edge, if there is at least one \(X\) left in that string. There is a perfect matching in this graph by Hall’s lemma, as \(m\) strings have to be matched with at least \(m\) letters: they contain \(m(N-K)\) characters in total, and there are only \((N-K)\) of each character remaining. This means that there exists some permutation \((X, Y, Z)\) of A, B, C, such that \(X\) is in the first string, \(Y\) in the second, \(Z\) in the last one. But then we would have taken it when we considered this permutation.

Complexity \(O(N)\).

Bonus: Can you split into \(5\) subsequences in such way?