The O(n) Club: Reorganize String (Or How to Avoid Awkward Repeats)

The O(n) Club: Reorganize String (Or How to Avoid Awkward Repeats)

⚡ TL;DR

Your string is throwing a party, but it can’t have two guests with the same name sitting together. Instead of brute-forcing every possible arrangement like a caffeinated octopus, just use a max-heap and a little mathematical sense:

// Java: Rearranges string or returns "" if impossible
public String reorganizeString(String s) {
    int[] freq = new int[26];
    for (char c : s.toCharArray()) freq[c - 'a']++;
    int max = 0, n = s.length();
    for (int f : freq) max = Math.max(max, f);
    if (max > (n + 1) / 2) return "";
    PriorityQueue
<character> pq = new PriorityQueue<>((a, b) -> freq[b - 'a'] - freq[a - 'a']);
    for (char c = 'a'; c <= 'z'; c++) if (freq[c - 'a'] > 0) pq.offer(c);
    StringBuilder sb = new StringBuilder();
    while (pq.size() > 1) {
        char a = pq.poll(), b = pq.poll();
        sb.append(a).append(b);
        if (--freq[a - 'a'] > 0) pq.offer(a);
        if (--freq[b - 'a'] > 0) pq.offer(b);
    }
    if (!pq.isEmpty()) sb.append(pq.poll());
    return sb.toString();
}
</character>

🧠 How Devs Usually Mess This Up

Most try shuffling like it’s Vegas, hoping to stumble on a valid combo—but that roulette pays out about as often. Some folks forget the critical check: if one character features more than half the time, it’s mathematically doomed. Blindly alternating after a frequency sort works… until all the ‘a’s form a conga line.

🔍 What’s Actually Going On

Picture musical chairs at a tech meetup, but every ‘a’ is the overzealous guy who always sits with himself. The secret: always plop the most frequent char available in a seat with the most space. If anyone claims more than half the seats, they’re banned from the room (or, in our case, just return “”). It’s all just strategic distribution—like task scheduling, but with fewer HR complaints.

🛠️ PseudoCode

• Count character frequencies

  // Java
  int[] freq = new int[26];
  for (char c : s.toCharArray()) freq[c - 'a']++;

  This is just keeping score: who wants to sit down, and how many times?

• Impossibility check

  if (maxFreq > (length + 1) / 2) return "";

  More than half means someone’s sitting by themselves—sad, but rules are rules.

• Max-heap for frequent characters

  PriorityQueue<character> pq = ...</character>

  So we always grab the loudest character first—heap keeps them in line.

• Greedy seat assignment

  while (pq.size() > 1) {
    char a = pq.poll(), b = pq.poll();
    append a, b;
    if (remaining) re-add;
  }

  Seats neighbors who aren’t twins and keeps leftovers for next round.

• Finish with the leftover

  if (!pq.isEmpty()) append last guy;

  One last loner? Toss them at the end—if they fit.

💻 The Code

import java.util.PriorityQueue;
 public class Solution {
    public String reorganizeString(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) freq[c - 'a']++;
        int max = 0, n = s.length();
        for (int f : freq) max = Math.max(max, f);
        if (max > (n + 1) / 2) return "";
        PriorityQueue
<character> pq = new PriorityQueue<>((a, b) -> freq[b - 'a'] - freq[a - 'a']);
        for (char c = 'a'; c <= 'z'; c++) if (freq[c - 'a'] > 0) pq.offer(c);
        StringBuilder sb = new StringBuilder();
        while (pq.size() > 1) {
            char a = pq.poll(), b = pq.poll();
            sb.append(a).append(b);
            if (--freq[a - 'a'] > 0) pq.offer(a);
            if (--freq[b - 'a'] > 0) pq.offer(b);
        }
        if (!pq.isEmpty()) sb.append(pq.poll());
        return sb.toString();
    }
}
</character>

⚠️ Pitfalls, Traps & Runtime Smacks

• The ‘off-by-one’ impossibility disaster: Remember, max is (N + 1) / 2—not N / 2, or the test case police will get you.
• Heap re-adds matter: Update and return chars back to heap after a use, or you’ll end up skipping popular kids.
• One-letter apocalypse: If the whole string is one character, don’t try to outsmart math—return empty string fast.
• Space: O(N) for result, O(1) for heap (unless the alphabet mutates overnight).

🧠 Interviewer Brain-Tattoo

“If the loudest guest can’t be separated from their twin, disinvite them. (Translation: return “” and move on.)”