まず、ある文字が \(S\) の過半数を占めている場合はどのように並べてもその文字が隣り合ってしまうため答えは No です。

実は、これ以外の場合は答えは Yes で条件を満たすように \(S\) を並び替えることができます。

並び替える方法はいくつかありますが、例えば以下のようなアルゴリズムで構成することができます：

• \(d[c]\) を文字 \(c\) の出現回数とする。
• \(T\) を空文字列とする。
• \(i=1,2,\ldots,|S|\) に対し、以下を順に行う：
  • \(T\) の末尾ではない文字の中で \(d[c]\) が最大となる \(c\) を選び、\(T\) に連結する。
  • \(d[c]\) を \(1\) 減らす。
• \(T\) が求める答えである。

以上を適切に実装することでこの問題に正答することができます。計算量は \(\sigma=26\) として \(O(\sigma |S|)\) です。

実装例(Python3)

import sys

input = sys.stdin.readline


def solve():
    s = input()[:-1]
    n = len(s)
    cnt = [0] * 26
    for c in s:
        cnt[ord(c) - ord("a")] += 1
    for v in cnt:
        if v > (n + 1) // 2:
            print("No")
            return
    ans = []
    prev = -1
    while True:
        idx = -1
        val = 0
        for i in range(26):
            if i == prev:
                continue
            if val < cnt[i]:
                val = cnt[i]
                idx = i
        if idx == -1:
            break
        ans.append(chr(ord("a") + idx))
        cnt[idx] -= 1
        prev = idx
    print("Yes")
    print("".join(ans))


for _ in range(int(input())):
    solve()