以下の方針で解くこともできます。ただし、\(N_1\) は \(N\) 以下の最大の奇数、\(N_2\) は \(N\) 以下の最大の偶数とします。

• \(1,3,5,\ldots,N_1,2,4,\ldots,N_2\) 文字目の順に出現回数の多いアルファベットを \(S'\) に順に入れていく。

例えば \(S=\) aabbbcc の場合、以下のように \(S'\) が構成されていきます：

• はじめ \(S'=\) ******* である。
• \(S\) の中のアルファベットを出現回数順に並べると、b が \(3\) 回、a が \(2\) 回、c が \(2\) 回である。
• b を \(S'\) にセットする。\(S'=\) b*b*b** となる。
• a を \(S'\) にセットする。\(S'=\) bab*b*a となる。
• c を \(S'\) にセットする。\(S'=\) babcbca となる。