The idea is simple: we only worry about the most frequent character(s).
ais the most frequent letter, so we start with a structure like
a  a  a  a 
and we just pad other letters in between the
a's. Only letters with the same highest frequency can go in to the last
. and we don't care about any letters with lower frequencies, we just scatter them among the paddings. So we end up with
a [bcdf] a [bcdg] a [bce] a [b].
If all the paddings except the last one have length larger than
k-1, then we have our answer; else we return
from collections import defaultdict class Solution(object): def rearrangeString(self, string, k): if not string: return '' count = defaultdict(int) for s in string: count[s] += 1 # sort the letters according to the frequency stack = sorted(list(count.items()), key=lambda t: t) char, count = stack.pop() # get most frequent character lst = [[char] for _ in range(count)] # take care of the letters with same highest freq while stack and stack[-1] == count: char, _ = stack.pop() for l in lst: l.append(char) # all the characters left res = ''.join(c*n for c, n in stack) # padding for i, r in enumerate(res): lst[i % (len(lst)-1)].append(r) for l in lst[:-1]: if len(l) < k: return '' return ''.join(''.join(l) for l in lst)