Algorithms/leetcode.com/python/358_Rearrange_String_k_Distance_Apart.py at master · bullshack/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from collections import Counter
import heapq

class Solution(object):
    def rearrangeString(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        if k == 0:
            return s
        result, priorityQueue = "", []
        charFrequencies = Counter(s)
        for key, value in charFrequencies.items():
            heapq.heappush(priorityQueue, (-value, key))
        while priorityQueue:
            tempCharHolder, currentDistance = [], 0
            while currentDistance < k:
                if priorityQueue:
                    currentDistance += 1
                    currentCharFrequency, currentChar = heapq.heappop(priorityQueue)
                    result += currentChar
                    if currentCharFrequency != -1:
                        tempCharHolder.append((currentCharFrequency + 1, currentChar))
                else:
                    if tempCharHolder:
                        return ""
                    else:
                        return result
            for item in tempCharHolder:
                heapq.heappush(priorityQueue, item)
        return result


sol = Solution()
# s = "aabbcc"
# k = 3
s = "aa"
k = 2
out = sol.rearrangeString(s, k)
print("res: ", out)