767. Reorganized String

Original Problem

Sanity Check Is Crucial

The approach isn't difficult. First, count occurrences of each character.

Then perform a time-saving sanity check:

$\text{frequency of some character} - \text{sum of frequencies of all other characters} \geq 2$

If this happens, it's impossible — return "" since no valid rearrangement exists.

How do we set threshold? Let $n$ be length of string.

When a character's frequency is $\frac{1 + n}{2}$, it's still within the limit.

But if it increases by $\frac{1}{2}$ to become $\frac{2 + n}{2}$, the difference becomes 2. A violation.

So sanity check should verify that no character's frequency exceeds $\frac{1 + n}{2}$.

After Passing Sanity Check

Place all characters into a max heap, where each element is in the format (remaining count, character).

As long as max heap has at least two elements:

pop top element $(Count_1, Char_1)$, then pop again to get $(Count_2, Char_2)$.

Use exactly one of each character per round:

append $Char_1$ and $Char_2$ to the unfinished reshapedString,

then push $(Count_1 - 1, Char_1)$ back only if $Count_1 - 1 > 0$.

Max heap is only for characters that haven't been exhausted yet.

Same logic applies to $(Count_2 - 1, Char_2)$.

When to Stop ✋🏻

When max heap has 0 or 1 element remaining:

I. If empty, return reshapedString immediately.

II. If one element remains, it must be exactly 1: because sanity check passed.

Append its character to the end of reshapedString and return.

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

Time complexity: $O(n \log k)$ where $n$ is string length and $k$ is number of distinct characters.

Space complexity: $O(n)$ where $n$ is string length.