If there exists a letter that occurs more than the half in \(S\), then any rearrangement would contain its consecutive occurrence, so the answer is No.

In fact, the answer is Yes for all the other cases; a valid rearrangement always exists.

There are several rearranging strategy; for example, the following algorithm constructs a valid one:

• Let \(d[c]\) be the frequency of letter \(c\).
• Let \(T\) be an empty string.
• For \(i=1,2,\ldots,|S|\), do the following:
  • Choose a letter \(c\) with the maximum \(d[c]\) among the characters that are not equal to the last character of \(T\), and append it to \(T\).
  • Subtract \(1\) from \(d[c]\).
• The resulting \(T\) is a sought answer.

The problem can be solved by appropriately implementing the algorithm above. The complexity is \(O(\sigma |S|)\), where \(\siamg=26\).

Sample code (Python 3)

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()