If there exists a letter that occurs more than \(\displaystyle \frac{|S|+1}{2}\) times 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 \(\sigma=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()