Reorganize String

How It Works

Reorganize String spreads characters so no two identical ones are adjacent, driven by a max-heap of character frequencies. Always place the most frequent remaining character — the one under the greatest scheduling pressure — but never the same character twice in a row. The mechanics: pop the top character, append it to the output, decrement its count, and hold it aside for one round while the next pop takes its place; then push the held character back if it still has occurrences left.

Feasibility has a clean test up front: if any character's count exceeds ceil(n/2), placement is impossible because there are not enough gaps to separate the copies. Each of the n placements does O(1) heap operations at O(log A) each — A being the alphabet size, at most 26 — so the total is O(n log A), effectively linear. Greedily relieving the biggest pile first is exactly what prevents dead ends.

Step-by-Step Visualization

Code

static String reorganizeString(String s) {
  int[] freq = new int[26];
  for (char c : s.toCharArray()) freq[c - 'a']++;

  PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
  for (int i = 0; i < 26; i++) if (freq[i] > 0) pq.add(new int[]{i, freq[i]});
  if (pq.peek()[1] > (s.length() + 1) / 2) return "";

  StringBuilder result = new StringBuilder();
  while (pq.size() > 1) {
    int[] first = pq.poll(), second = pq.poll();
    result.append((char)('a' + first[0]));
    result.append((char)('a' + second[0]));
    if (--first[1] > 0) pq.add(first);
    if (--second[1] > 0) pq.add(second);
  }
  if (!pq.isEmpty()) result.append((char)('a' + pq.poll()[0]));
  return result.toString();
}

Tips & Gotchas

Practice Problems

• 1Reorganize String
• 2Task Scheduler
• 3Distant Barcodes
• 4Rearrange String k Distance Apart

About the Reorganize / Schedule Pattern

Use a max-heap to always process the most frequent item first. After processing, apply a cooldown before it can be used again. This greedy approach minimizes idle gaps or spreads characters apart.

Common Heap Interview Problems

• Kth Largest Element
• Top K Frequent Elements
• Find Median from Data Stream
• Merge K Sorted Lists
• Task Scheduler
• K Closest Points to Origin

Frequently Asked Questions

Other Reorganize / Schedule Techniques