Reorganize String

Problem Statement

Given a string s, return any permutation such that no two adjacent characters are equal. If impossible, return the empty string.

Input

A lowercase string s.

s = "aaabbc"

Output

Any valid rearrangement, or "" if none exists.

"ababac"   // or "abacab" — any valid permutation

Constraints

• 1 ≤ s.length ≤ 500
• s consists of lowercase English letters.

Intuition

Greedy: always place the character with the highest remaining count — unless it’s the same as the previous one, in which case place the next-best. Use a max-heap keyed on frequency. Pop the top, append to output, decrement, and don’t push it back immediately — stash it as “just used”. On the next iteration, pop the new top, then push the stash back in. This guarantees no two consecutive picks are the same character.

Feasibility check: if any character has frequency greater than ⌈n / 2⌉, no valid arrangement exists.

freq: {a:3, b:2, c:1}    max_freq=3 ≤ ⌈6/2⌉=3   → feasible
 
heap (max): [(3,a),(2,b),(1,c)]    prev = (0, "")
pop (3,a) → emit 'a' → prev=(2,a)   heap=[(2,b),(1,c)]
pop (2,b) → emit 'b' → push prev → prev=(1,b)   heap=[(2,a),(1,c)]
pop (2,a) → emit 'a' → push prev → prev=(1,a)   heap=[(1,b),(1,c)]
pop (1,b) → emit 'b' → push prev → prev=(0,b)   heap=[(1,a),(1,c)]  // prev_cnt==0 → drop
pop (1,a) → emit 'a' → push prev (0) dropped → prev=(0,a)   heap=[(1,c)]
pop (1,c) → emit 'c' → prev=(0,c)   heap=[]
 
result = "ababac" ✓

Solution

import heapq
from collections import Counter
 
def reorganizeString(s: str) -> str:
    freq = Counter(s)
    if max(freq.values()) > (len(s) + 1) // 2:
        return ""                                   # infeasible
 
    max_heap = [(-cnt, ch) for ch, cnt in freq.items()]
    heapq.heapify(max_heap)
 
    result: list[str] = []
    prev_cnt, prev_ch = 0, ""                       # "just used" stash
 
    while max_heap:
        cnt, ch = heapq.heappop(max_heap)           # cnt is negative
        result.append(ch)
        if prev_cnt < 0:
            heapq.heappush(max_heap, (prev_cnt, prev_ch))
        prev_cnt, prev_ch = cnt + 1, ch             # increment toward 0
 
    return "".join(result)

function reorganizeString(s: string): string {
  const freq = new Map<string, number>();
  for (const c of s) freq.set(c, (freq.get(c) ?? 0) + 1);
 
  let maxF = 0;
  for (const v of freq.values()) maxF = Math.max(maxF, v);
  if (maxF > Math.ceil(s.length / 2)) return "";
 
  // max-heap by count
  const h = new Heap<[number, string]>((a, b) => b[0] - a[0]);
  for (const [ch, cnt] of freq) h.push([cnt, ch]);
 
  const out: string[] = [];
  let prev: [number, string] | null = null;
 
  while (h.size > 0) {
    const [cnt, ch] = h.pop()!;
    out.push(ch);
    if (prev && prev[0] > 0) h.push(prev);
    prev = [cnt - 1, ch];
  }
  return out.join("");
}

Complexity

Edge Case Thinking