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] 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] * max_num del dic[all_chars] 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.