\(S\) に最も多く現れる文字が a であるとしてよいです。 a が \(A\) 回、その他の文字が合計 \(B\) 回現れるとします。

\(A \le B\) のとき

この場合 \(f(S') = 0\) とすることができます。\(f(S') = 0\) は \(S'\) において同じ文字が隣接しないことと同値であり、これは次のような並べ替えによって実現できます：

• \(S\) の文字を並べ替えて a, b, \(\ldots\) z がこの順に現れるようにした文字列を \(S_0\) とする。
• \(S_0\) の文字を前から順に、\(1\) 文字目、\(3\) 文字目、\(5\) 文字目、\(\ldots\) と奇数番目に順番に配置していく。奇数番目に置けなくなったら \(2\) 文字目、\(4\) 文字目、\(\ldots\) と偶数番目に配置していく。得られた文字列を \(S'\) とする。

例えば \(S =\) abracadabra のとき \(S_0 =\) aaaaabbcdrr であり、\(S' =\) abacadararb となります。

\(A > B\) のとき

英小文字からなる文字列 \(s\) に対し、\(s\) における a のみからなる偶数長の部分文字列の個数を \(\tilde{f}(s)\) で表すことにします。明らかに \(\tilde{f}(s) \leq f(s)\) です。以下の二つの条件を満たすような \(S'\) を \(1\) つ構成することができれば、それが答えになります。

• \(S'\) は \(S\) の文字を並べ替えて得られる文字列のうち、\(\tilde{f}(S')\) が最小になるもの（の一つ）である。
• \(\tilde{f}(S') = f(S')\) が成り立つ。

まず \(\tilde{f}\) の性質について調べます。以降、\(s\) が a を \(n\) 個並べた文字列であるときの \(\tilde{f}(s)\) の値を \(a(n)\) で表します。\(m \geq 0\) に対し \(a(2m) = m^2, a(2m + 1) = m(m+1)\) となるため、\(a(n)\) は以下を満たします。

• 性質1：\(a(n)\) は下に凸である。すなわち、任意の \(n \geq 1\) に対し \(2a(n) \leq a(n-1) + a(n+1)\) である。
• 性質 2：\(n\) が正の偶数のとき \(2a(n) = a(n-1) + a(n+1)\) である。

\(S\) を並べ替えて得られる \(S'\) について、a 以外の文字で \(S'\) を分割すると、a のみからなる文字列が \(B+1\) 個得られます（例えば axaaxay からは a, aa, a, 空文字列が得られます）。これらの長さを（前から順に）\(n_1, n_2, \dots, n_{B+1}\) とおくと、\(\tilde{f}(S') = \sum_{i = 1}^{B+1} a(n_i)\) となります。

性質 1 より、\(n_i\) をなるべく均等にしたときに \(\tilde{f}\) が最小になります。具体的には、\(A = q(B + 1) + r \, (q, r\) は整数で \(0 \leq r \leq B)\) と表したとき、\(n_1 = \dots = n_r = q + 1, n_{r + 1} = \dots = n_{B+1} = q\) とすると \(\tilde{f}(S')\) が最小になります。

一般にこのような並べ替え方について \(\tilde{f}(S') = f(S')\) となるとは限りません。しかし、性質 2 を用いると、「\(n_i\) に偶数が \(2\) 個（以上）含まれるならば、一方は \(1\) 増やし、もう一方は \(1\) 減らして両方奇数にする」ことを繰り返し、\(\tilde{f}(S')\) を最小に保ったまま \(n_2, \dots, n_{B+1}\) をすべて奇数にすることができます。このとき \(S'\) には \(a\) のみからなる偶数長の部分文字列以外に偶数長の回文である部分文字列は含まれないため、\(\tilde{f}(S') = f(S')\) となります。

以上で最適な \(S'\) を構成することができました。