Pseudo-code:

text
function solve(s):
    permutations = generate_all_permutations(s)
    for p in permutations:
        valid = true
        for i from 1 to length(p) - 1:
            if p[i] == p[i-1]:
                valid = false
                break
        if valid:
            return p
    return ""

Why this fails: The time complexity of this approach is $O(N \cdot N!)$, where $N$ is the length of the string. With the constraint $N \le 500$, the number of permutations is astronomically large ($500!$). This will immediately result in a Time Limit Exceeded (TLE) error. We need a constructive approach rather than a search-based approach.

Core Insight for Reorganize String

The fundamental intuition for the LeetCode 767 solution is based on the Greedy Principle. To minimize the risk of running out of "buffer" characters to place between identical characters, we should always try to place the character that has the highest remaining frequency.

If the most frequent character appears more than $\lceil (N+1)/2 \rceil$ times, it is mathematically impossible to rearrange the string without adjacent duplicates (by the Pigeonhole Principle). We can return "" immediately in this case.

If a valid arrangement is possible, we use a Max-Heap to manage character frequencies.

1. Selection: At each step, we extract the character with the highest count from the heap.
2. Constraint: We cannot simply put this character back into the heap immediately, or we might pick it again in the very next step, violating the adjacency rule.
3. Scheduling: We must "hold" or "block" the character we just used. We only push it back into the heap after we have picked a different character in the subsequent step.

Visual Description: Imagine the heap as a dynamic ranking board. At the top is the character with the most urgent need to be placed.

1. We pull the top item (e.g., 'a' with count 5).
2. We place 'a' in our result.
3. We temporarily hold 'a' (now count 4) in a "waiting room" variable.
4. We pull the new top item from the heap (e.g., 'b' with count 3).
5. We place 'b'.
6. Now that we have placed 'b', 'a' is no longer adjacent to the current position. We move 'a' from the "waiting room" back into the heap.

Execution Flow

Let's trace s = "aab".

• Counts: {'a': 2, 'b': 1}.
• Heap: [(2, 'a'), (1, 'b')]. prev is None.

Iteration 1:

1. Pop max: (2, 'a').
2. Result: "a".
3. Decrement count: (1, 'a').
4. prev was None, so nothing is pushed back.
5. Set prev = (1, 'a').
6. Heap is now [(1, 'b')].

Iteration 2:

1. Pop max: (1, 'b').
2. Result: "ab".
3. Decrement count: (0, 'b').
4. prev was (1, 'a'). Push (1, 'a') back to heap.
5. Set prev = (0, 'b').
6. Heap is now [(1, 'a')].

Iteration 3:

1. Pop max: (1, 'a').
2. Result: "aba".
3. Decrement count: (0, 'a').
4. prev was (0, 'b'). Count is 0, so do not push back.
5. Set prev = (0, 'a').
6. Heap is empty.

End: Heap empty. Return "aba".

Proof of Correctness

The correctness relies on the invariant that we always reduce the count of the most frequent character. By always picking the element with the highest remaining frequency, we ensure that the most "problematic" character (the one most likely to cause a collision) is spaced out as evenly as possible. The "hold and push back" mechanism guarantees strictly that $result[i] \neq result[i-1]$.

If the maximum frequency constraint ($count(c) \le (N+1)/2$) holds, a valid arrangement always exists. The greedy strategy constructs one such arrangement by ensuring we never leave a high-frequency character stranded at the end without valid separators.

Reference Implementation

C++ Solution for LeetCode 767

cpp
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> counts;
        for (char c : s) {
            counts[c]++;
        }

        // Max-heap storing pairs of (frequency, character)
        priority_queue<pair<int, char>> pq;
        for (auto& entry : counts) {
            // Early exit check: if any char count > (N + 1) / 2, impossible
            if (entry.second > (s.length() + 1) / 2) {
                return "";
            }
            pq.push({entry.second, entry.first});
        }

        string result = "";
        pair<int, char> prev = {-1, '#'}; // Placeholder for blocked char

        while (!pq.empty()) {
            pair<int, char> current = pq.top();
            pq.pop();

            result += current.second;
            current.first--;

            // If we have a valid previous character blocked, put it back
            if (prev.first > 0) {
                pq.push(prev);
            }

            // Block the current character for the next iteration
            prev = current;
        }

        if (result.length() != s.length()) {
            return "";
        }

        return result;
    }
};

Java Solution for LeetCode 767

java
import java.util.PriorityQueue;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public String reorganizeString(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }

        // Max-heap ordered by frequency descending
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);

        for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > (s.length() + 1) / 2) {
                return "";
            }
            // Store as [count, char_code]
            pq.offer(new int[]{entry.getValue(), entry.getKey()});
        }

        StringBuilder sb = new StringBuilder();
        int[] prev = null; // Holds the character blocked from immediate reuse

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            
            sb.append((char)current[1]);
            current[0]--;

            // If there was a previous character waiting, add it back to heap
            if (prev != null && prev[0] > 0) {
                pq.offer(prev);
            }

            // Block current character
            prev = current;
        }

        if (sb.length() != s.length()) return "";
        return sb.toString();
    }
}

Python Solution for LeetCode 767

python
import heapq
from collections import Counter

class Solution:
    def reorganizeString(self, s: str) -> str:
        counts = Counter(s)
        
        # Python's heapq is a min-heap. We store negative counts to simulate max-heap.
        max_heap = []
        for char, count in counts.items():
            if count > (len(s) + 1) / 2:
                return ""
            heapq.heappush(max_heap, (-count, char))
            
        result = []
        prev_count, prev_char = 0, ''
        
        while max_heap:
            count, char = heapq.heappop(max_heap)
            
            result.append(char)
            
            # Since count is negative, we add 1 to decrement frequency towards 0
            count += 1
            
            # If the PREVIOUS character still has count left, push it back
            if prev_count < 0:
                heapq.heappush(max_heap, (prev_count, prev_char))
            
            # Update previous to current
            prev_count, prev_char = count, char
            
        final_str = "".join(result)
        if len(final_str) != len(s):
            return ""
            
        return final_str