Straightforward Python Solution, 98%

  • 1

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

Log in to reply

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