https://leetcode.com/problems/rearrange-string-k-distance-apart/description/

rearrange-string-k-distance-apart.py

class Solution(object):
    
    def addString(self, prefix, s, k, chars):
        print 'AddString({},{},{},{})'.format(prefix, s, k, chars)
        if len(prefix) == len(s):
            return prefix
        for (c,n) in chars.items():
            # print prefix[-k+1:]
            if c not in prefix[-k+1:] and n > 0:
                chars[c] -= 1
                answer = self.addString(prefix + c, s, k, chars)
                chars[c] += 1
                if answer:
                    return answer
        return ''
    
    def rearrangeString(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        char_set = collections.Counter(c for c in s)
        if len(s) == 1 or k <= 1:
            return s
        if len(char_set) < k:
            return ''
        result = ''
        for (c,n) in char_set.items():
            char_set[c] -= 1
            answer = self.addString(c, s, k, char_set)
            char_set[c] += 1
            if answer:
                return answer
        return ''