# Straightforward Python Solution, 98%

• The idea is simple: we only worry about the most frequent character(s).
For example `aaaabbbbcccddefg`, `a`is 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[1])

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][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)