Code Implementation

import heapq
from collections import Counter

class Solution:
    def reorganizeString(self, s: str) -> str:
        count = Counter(s)
        max_heap = [(-freq, char) for char, freq in count.items()]
        heapq.heapify(max_heap)
        prev_freq, prev_char = 0, ''
        result = []

        while max_heap:
            freq, char = heapq.heappop(max_heap)
            result.append(char)
            if prev_freq < 0:
                heapq.heappush(max_heap, (prev_freq, prev_char))
            freq += 1  # since freq is negative
            prev_freq, prev_char = freq, char

        reorganized = ''.join(result)
        for i in range(1, len(reorganized)):
            if reorganized[i] == reorganized[i-1]:
                return ""
        return reorganized
      

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

class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> count;
        for (char c : s) count[c]++;
        priority_queue<pair<int, char>> maxHeap;
        for (auto& it : count) {
            maxHeap.push({it.second, it.first});
        }
        string result = "";
        pair<int, char> prev = {0, ' '};
        while (!maxHeap.empty()) {
            auto curr = maxHeap.top(); maxHeap.pop();
            result += curr.second;
            if (prev.first > 0) {
                maxHeap.push(prev);
            }
            curr.first--;
            prev = curr;
        }
        for (int i = 1; i < result.size(); ++i) {
            if (result[i] == result[i-1]) return "";
        }
        return result;
    }
};
      

import java.util.*;

class Solution {
    public String reorganizeString(String s) {
        Map<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray())
            count.put(c, count.getOrDefault(c, 0) + 1);
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (char c : count.keySet())
            maxHeap.add(new int[]{count.get(c), c});
        StringBuilder result = new StringBuilder();
        int[] prev = {0, ' '};
        while (!maxHeap.isEmpty()) {
            int[] curr = maxHeap.poll();
            result.append((char)curr[1]);
            if (prev[0] > 0)
                maxHeap.add(prev);
            curr[0]--;
            prev = curr;
        }
        for (int i = 1; i < result.length(); i++) {
            if (result.charAt(i) == result.charAt(i-1)) return "";
        }
        return result.toString();
    }
}
      

function reorganizeString(s) {
    const count = {};
    for (const c of s) count[c] = (count[c] || 0) + 1;
    const maxHeap = [];
    for (const c in count) maxHeap.push([count[c], c]);
    maxHeap.sort((a, b) => b[0] - a[0]);
    let prev = [0, ''];
    let result = '';
    while (maxHeap.length > 0) {
        let curr = maxHeap.shift();
        result += curr[1];
        if (prev[0] > 0) maxHeap.push(prev);
        curr[0]--;
        prev = curr;
        maxHeap.sort((a, b) => b[0] - a[0]);
    }
    for (let i = 1; i < result.length; ++i) {
        if (result[i] === result[i-1]) return '';
    }
    return result;
}
      

Problem Description

Given a string s, rearrange its characters so that no two adjacent characters are the same. If it is not possible to do so, return an empty string "". Each character from s must be used exactly once in the result.

• Input: a string s consisting of lowercase English letters.
• Output: a rearranged string where no two identical characters are adjacent, or "" if impossible.
• Constraints: All characters from s must be used, and each appears exactly as many times as in the original string.

Thought Process

At first glance, the problem seems to ask for all possible rearrangements and to check which one meets the requirement that no two adjacent characters are the same. However, generating all permutations would be extremely inefficient for longer strings.

Instead, we can observe that the main challenge is to prevent high-frequency characters from being adjacent. If a character appears more than half the length of the string (rounded up), it's impossible to separate them, so we can quickly check this as a base case.

To build a valid string efficiently, we should always place the most frequent character available, but not directly after itself. We can use a max heap (priority queue) to always pick the character with the highest remaining count, and alternate between the top two characters to avoid adjacency.

Solution Approach

• Step 1: Count Character Frequencies
  Use a hash map or array to count how many times each character appears in s.
• Step 2: Build a Max Heap
  Create a max heap (priority queue) where each entry is a pair of (frequency, character). This allows us to always select the character with the highest remaining count.
• Step 3: Construct the Result String
  While the heap is not empty:
  • Pop the character with the highest frequency.
  • Append it to the result string.
  • If there's a previously used character (from the last round) that still has remaining count, push it back into the heap.
  • Decrease the count of the current character and set it as the 'previous' for the next round.
• Step 4: Check for Validity
  After building the string, verify that no two adjacent characters are the same. If so, return the string; otherwise, return an empty string.
• Why This Works
  By always choosing the most frequent character not used in the previous round, we ensure that high-frequency characters are spaced out as much as possible, preventing adjacency violations.

Example Walkthrough

Input: s = "aab"

• Count: {'a': 2, 'b': 1}
• Heap: [(2, 'a'), (1, 'b')]
• First iteration:
  • Pop ('a', 2): result = "a"
  • Decrease 'a' count to 1; prev = ('a', 1)
• Second iteration:
  • Pop ('b', 1): result = "ab"
  • Push prev ('a', 1) back into heap
  • Decrease 'b' count to 0; prev = ('b', 0)
• Third iteration:
  • Pop ('a', 1): result = "aba"
  • 'a' count is now 0; no more to push back
• Heap is empty. Result is "aba", which has no adjacent identical characters.

Output: "aba"

Time and Space Complexity

• Brute-force approach: Generating all permutations is O(n!), which is infeasible for large n.
• Optimized approach:
  • Time Complexity: O(n log k), where n is the length of the string and k is the number of unique characters. Each heap operation is O(log k) and we do up to n operations.
  • Space Complexity: O(n + k), for the result string and frequency map/heap.

Summary

The key insight is to always pick the most frequent character available, while ensuring no two identical characters are adjacent. Using a max heap allows us to efficiently select and alternate characters, spacing out high-frequency letters. This greedy approach is both efficient and elegant, avoiding the pitfalls of brute-force permutation generation.