Submission #76079967

---

Source Code Expand

def stack_gen(arg, inf = False):
    for i, n in arg:
        for _ in range(n):yield i
    while inf:
        yield ""
    return ""
from collections import defaultdict
T = int(input())
for _ in range(T):
    S = input()
    roof = (len(S)+1)//2
    max_v = 0
    s_dic = defaultdict(int)
    for Si in S:
        s_dic[Si]+=1
        max_v = max(max_v, s_dic[Si])
        if max_v>roof:
            print("No")
            break
    else:
        print("Yes")
        s_sort = sorted(s_dic.items(), key = lambda i:i[1], reverse = True)
        outsides = []
        outside_len = 0
        for n, i in enumerate(s_sort):
            if outside_len+i[1]>roof:
                left_out = roof-outside_len
                last = (n, (i[0], i[1]-left_out))
                outsides.append((i[0], left_out))
                break
            outside_len+=i[1]
            outsides.append(i)
        s_sort[last[0]] = last[1]
        insides = s_sort[last[0]:]
        print("".join(i+jj for i, jj in zip(stack_gen(outsides), stack_gen(insides, inf = True),)))

Submission Info

Judge Result