Super intuitive Python solution, O(log(26) * n) time with explanation


  • 0
    Y
    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 ""
    
    1. 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:
    2. If k * (max_num - 1) + len(max_char) > len(str), there is no way to make it, return "".
    3. 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.
    4. When we have put all characters, done.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.