```
class Solution(object):
def rearrangeString(self, str, k):
"""
:type str: str
:type k: int
:rtype: str
"""
if k == 1:
return str
dic = collections.defaultdict(int)
for c in str:
dic[c] += 1
all_chars = sorted(dic.keys(), key = lambda x: dic[x], reverse = True)
max_num = dic[all_chars[0]]
max_char = set()
for c in dic:
if dic[c] == max_num:
max_char.add(c)
if (max_num - 1) * k + len(max_char) <= len(str):
res = [all_chars[0]] * max_num
del dic[all_chars[0]]
pos, pos_res = 0, 0
while dic:
c = all_chars[pos_res]
if c in dic:
res[pos] += c
if c in max_char:
pos = (pos + 1) % max_num
else:
pos = (pos + 1) % (max_num - 1)
dic[c] -= 1
if dic[c] == 0:
del dic[c]
else:
pos_res = pos_res+1
return "".join(res)
else:
return ""
```

- Find the character with maximal number, it might be a few, put them in a set called max_char with number max_num, put the number of each character in a dict called dic:
- If k * (max_num - 1) + len(max_char) > len(str), there is no way to make it, return "".
- If we can make it, put each character into a str in res, from the most frequent one to the least frequent one.

Also notice, if the character also has the same number as the max_num, we need to consider the position in the last str, otherwise we don't consider it.
- When we have put all characters, done.