767. Reorganize String

https://leetcode.com/problems/reorganize-string/

solution

• 大顶堆，堆中的元素是(频率，字母)

• reference

class Solution:
    def reorganizeString(self, s: str) -> str:
        # 先最多，第二多，继续最多，第二多
        counter = collections.defaultdict(int)
        for char in s:
            counter[char] += 1

        heap = []
        for char, freq in counter.items():
            heapq.heappush(heap, [-freq, char])

        res = []
        while len(heap) > 1:
            f1, char1 = heapq.heappop(heap)
            f2, char2 = heapq.heappop(heap)
            if f1 < -1:
                heapq.heappush(heap, [f1+1, char1])
            if f2 < -1:
                heapq.heappush(heap, [f2+1, char2])
            res.append(char1)
            res.append(char2)
        if heap:
            if heap[0][0] < -1:
                return ""
            res.append(heapq.heappop(heap)[1])
        return "".join(res)

时间复杂度：O() 空间复杂度：O()

class Solution:
    def reorganizeString(self, s: str) -> str:
        counter = collections.defaultdict(int)
        for char in s:
            counter[char] += 1

        heap = []
        for char, freq in counter.items():
            heapq.heappush(heap, (-freq, char))

        prev_freq = 0  # 显式保留并记录上一个的频率和字母, 下一个pop后重新考虑上一任
        prev_char = ''
        res = []
        while heap:
            freq, char = heapq.heappop(heap)
            res.append(char)
            if prev_freq < 0:
                heapq.heappush(heap, (prev_freq, prev_char))

            prev_freq = freq + 1
            prev_char = char

        return "".join(res) if len(res) == len(s) else ''