767. Reorganized String

原题在这边

Sanity Check非常重要的

思路不难 我们先把每个字符出现的次数统计出来

好好地来一个 节省未来时间的防呆检查：

$\text{某个字符的出现频率} - \text{其他字符出现频率之和} \geq$ 2

那这绝对就没招了 只能回个"" 没法重组出相邻字符不重复字串

至于如何画出筛选门槛呢？ 若$n$为字串长度

$\frac{1 + n}{2} - (n - \frac{1 + n}{2}) = 1$

字符出现频率在$\frac{1 + n}{2}$时还没犯规

但如果再加$\frac{1}{2}$变成$\frac{2 + n}{2}$

刚才的差值就变成是2 犯规啦

因此防呆检查要判断有无字符出现频率 超过$\frac{1 + n}{2}$

确认Sanity Check没事后

把全部字符放在一个Max Heap里 这大堆中每个元素都是 (剩馀次数, 字符) 这样的格式

只要大堆还有起码两元素

就先把堆顶元素$(Count_1, Char_1)$取出来

接著再取一遍堆顶元素$(Count_2, Char_2)$

然后每次俩字符都各只用一个而已

把$Char_1$和$Char_2$拼接到未完成的reshapedString上

再请$(Count_1 - 1, Char_1)$入堆 前提是$Count_1 - 1 > 0$

毕竟大堆是拿来给还没耗光的字符啰

$(Count_2 - 1, Char_2)$同理

何时收手呢✋🏻

就是大堆内只剩下 零或一个 元素时：

I. 没剩元素肯定能立刻回传reshapedString

II. 要是还有剩 肯定等于1 因为上方有通过Sanity Check啦

把元素上字符接到reshapedString末尾即可回传

C++

#include <queue>
#include <string>
#include <unordered_map>
using namespace std;

string reorganizeString(string initString) // LeetCode Q.767.
{
    unordered_map<char, int> charsCounts;

    for (const char& character : initString) {
        charsCounts[character]++;

        // Sanity check.
        if (charsCounts[character] > (initString.size() + 1) / 2)
            return "";
    }

    priority_queue<pair<int, char>> maxHeap; // Format: {count, char}.

    for (const auto& [character, count] : charsCounts)
        maxHeap.push({count, character});

    string reshapedString = "";

    while (maxHeap.size() > 1) {
        const auto [topOneCount, topOneChar] = maxHeap.top();
        maxHeap.pop();

        const auto [topTwoCount, topTwoChar] = maxHeap.top();
        maxHeap.pop();

        reshapedString += topOneChar;
        reshapedString += topTwoChar;

        if (topOneCount > 1)
            maxHeap.push({topOneCount - 1, topOneChar});

        if (topTwoCount > 1)
            maxHeap.push({topTwoCount - 1, topTwoChar});
    }

    if (!maxHeap.empty())
        reshapedString += maxHeap.top().second;

    return reshapedString;
}

Python

import heapq


def reorganize_string(init_string: str) -> str:  # LeetCode Q.767.
    chars_counts: dict[str, int] = dict()

    for char in init_string:
        if char not in chars_counts.keys():
            chars_counts.update({char: 0})
        chars_counts[char] += 1

        # Sanity check.
        if chars_counts[char] > (len(init_string) + 1) / 2: return ""

    max_heap: list[tuple[int, str]] = []  # Format: (count, char).

    for char, count in chars_counts.items():
        heapq.heappush(max_heap, (-count, char))  # Negate count to fit max heap.

    reshaped_string = ""

    while len(max_heap) > 1:
        top_1_count, top_1_char = heapq.heappop(max_heap)
        top_1_count = -top_1_count  # Negate back to original value.

        top_2_count, top_2_char = heapq.heappop(max_heap)
        top_2_count = -top_2_count  # Negate back to original value.

        reshaped_string += top_1_char + top_2_char

        if top_1_count > 1:  # Negate count to fit max heap.
            heapq.heappush(max_heap, (1 - top_1_count, top_1_char))

        if top_2_count > 1:  # Negate count to fit max heap.
            heapq.heappush(max_heap, (1 - top_2_count, top_2_char))

    if max_heap: reshaped_string += max_heap[-1][1]

    return reshaped_string

时间复杂度：$O(nlogk)$ 字串长度$n$ 字符种类数$k$

空间复杂度：$O(n)$ $n$是字串长度