Reorganize String

Reorganize String asks you to rearrange letters so no two same letters sit next to each other. It sounds like a puzzle. But it hides a clean idea. The letter that appears the most is the most dangerous. So you must place it first, while there is still room. A heap lets you always reach for the most common letter. That is the trick the interviewer wants.

🎯 The Problem

You get a string, and you must spread the letters apart. Here are the rules.

• Rearrange the letters so no two neighbours are the same letter.
• You may reorder the letters in any way.
• If no valid arrangement exists, return an empty string.
• The answer is any one valid arrangement, not a special one.

So "aab" can become "aba". The two a letters are now apart. But "aaab" cannot work. There are three a letters and only one other letter. You can never keep all three a letters apart. So you return "".

Input:  s = "aab"
Output: "aba"

Explanation: the two 'a' letters are separated by 'b'

The whole thing depends on the frequency of each letter. Frequency means how many times a letter appears. If one letter appears more than half the time (rounded up), it is impossible. Otherwise you can always arrange it.

The picture below shows the counts for "aab". The most frequent letter must go down first.

🐢 Approach 1: Try Every Arrangement (Brute Force)

The idea in one line: generate arrangements until one has no equal neighbours.

The idea:

• Make permutations of the string.
• Check each for two equal letters side by side.
• The first valid one is your answer.

How it works:

• It works for tiny strings.
• It does find an answer if one exists.

Why it is weak:

• A string of length n has up to n factorial arrangements.
• This is factorial time.
• It is hopeless for anything but the smallest input.

Here is the permutation-style brute-force code:

from itertools import permutations


def reorganize_string(s):
    for order in set(permutations(s)):
        if all(order[i] != order[i - 1] for i in range(1, len(order))):
            return "".join(order)
    return ""

🐌 Approach 2: Count and Fill Slots (Better)

The idea in one line: place the most frequent letter into the even slots first, then fill the rest.

The idea:

• Count each letter.
• Find the letter with the highest count.
• Drop that letter into positions 0, 2, 4, and so on. Then continue the other letters.

How it works:

• Even slots are never neighbours. So the busy letter never touches itself.
• When the even slots run out, keep going into the odd slots.

Why it is better:

• It runs in O(n) time. No heap needed.
• But it is fiddly to get the slot order right.
• If the top count is more than (n + 1) / 2, return the empty string.

Here is the count-and-fill-slots code:

from collections import Counter


def reorganize_string(s):
    counts = Counter(s)
    ch, freq = counts.most_common(1)[0]
    if freq > (len(s) + 1) // 2:
        return ""

    answer = [""] * len(s)
    index = 0
    for ch, freq in counts.most_common():
        for _ in range(freq):
            if index >= len(s):
                index = 1
            answer[index] = ch
            index += 2
    return "".join(answer)

⚡ Approach 3: Greedy With a Max-Heap (Best)

The idea in one line: always place the letter with the most copies left, and hold it aside for one step.

The idea:

• Place the letter that has the most remaining copies.
• That letter is the hardest to fit. Save it for last and you get stuck with two in a row.
• So place the most common one early and often.

The heap and the catch:

• A max-heap always hands you the largest item first. Here largest means highest count.
• You cannot place the same letter twice in a row.
• So hold the letter you just used aside for one step.

How one step works:

• Pop the top letter. Append it to the result. Lower its count by one.
• Push the held letter from last step back into the heap now.
• Move the letter you just used into the held slot.

How it finishes:

• Keep going until the heap is empty.
• If the result is shorter than the input, some letter could not be placed. Return "".

Why it is fast:

• Each letter copy is pushed and popped once.
• Each heap step costs O(log k), where k is the distinct letters. So the run is O(n log k).

The diagram below shows the place-then-hold dance.

Steps to Solve

1. Count how many times each letter appears.
2. Put every letter with its count into a max-heap, ordered by count.
3. Keep a “previous” slot empty at first. It holds the letter you just placed.
4. Pop the top letter. Append it to the result. Lower its count by one.
5. If the previous slot holds a letter with count above zero, push it back into the heap now.
6. Move the letter you just used into the previous slot.
7. Repeat until the heap is empty. If the result is shorter than the input, return "". Otherwise return the result.

#include <stdio.h>
#include <string.h>

void reorganize(const char *s, char *out) {
    int count[26] = {0};
    int n = strlen(s);
    for (int i = 0; i < n; i++) count[s[i] - 'a']++;

    int pos = 0;
    int prev = -1;  // letter placed last step, may not repeat now
    for (int k = 0; k < n; k++) {
        int best = -1;
        // pick most frequent letter that is not prev
        for (int c = 0; c < 26; c++) {
            if (c == prev) continue;
            if (count[c] > 0 && (best == -1 || count[c] > count[best])) {
                best = c;
            }
        }
        if (best == -1) {        // nothing valid to place
            out[0] = '\0';
            return;
        }
        out[pos++] = 'a' + best;
        count[best]--;
        prev = best;             // cannot use this letter next step
    }
    out[pos] = '\0';
}

int main(void) {
    char out[100];
    reorganize("aab", out);
    printf("%s\n", out[0] ? out : "\"\"");  // aba
    reorganize("aaab", out);
    printf("%s\n", out[0] ? out : "\"\"");  // ""
    return 0;
}

aba
""

#include <iostream>
#include <string>
#include <queue>
#include <vector>
using namespace std;

string reorganize(const string &s) {
    int count[26] = {0};
    for (char c : s) count[c - 'a']++;

    // max-heap of (count, letter)
    priority_queue<pair<int,char>> heap;
    for (int c = 0; c < 26; c++)
        if (count[c] > 0) heap.push({count[c], (char)('a' + c)});

    string result = "";
    pair<int,char> prev = {0, ' '};  // held letter from last step
    while (!heap.empty()) {
        auto cur = heap.top(); heap.pop();   // most frequent now
        result += cur.second;
        cur.first--;
        if (prev.first > 0) heap.push(prev); // put back the held letter
        prev = cur;                          // hold current for next step
    }
    return (int)result.size() == (int)s.size() ? result : "";
}

int main() {
    string a = reorganize("aab");
    cout << (a.empty() ? "\"\"" : a) << endl;   // aba
    string b = reorganize("aaab");
    cout << (b.empty() ? "\"\"" : b) << endl;   // ""
    return 0;
}

aba
""

import java.util.*;

public class ReorganizeString {
    public static String reorganize(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;

        // max-heap of int[]{count, letter}, biggest count on top
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int c = 0; c < 26; c++)
            if (count[c] > 0) heap.offer(new int[]{count[c], c});

        StringBuilder result = new StringBuilder();
        int[] prev = null;                  // held letter from last step
        while (!heap.isEmpty()) {
            int[] cur = heap.poll();        // most frequent now
            result.append((char) ('a' + cur[1]));
            cur[0]--;
            if (prev != null && prev[0] > 0) heap.offer(prev); // put held back
            prev = cur;                     // hold current for next step
        }
        return result.length() == s.length() ? result.toString() : "";
    }

    public static void main(String[] args) {
        String a = reorganize("aab");
        System.out.println(a.isEmpty() ? "\"\"" : a);   // aba
        String b = reorganize("aaab");
        System.out.println(b.isEmpty() ? "\"\"" : b);   // ""
    }
}

aba
""

import heapq
from collections import Counter


def reorganize(s):
    counts = Counter(s)                 # letter -> how many times
    # min-heap on negative count = max-heap on count
    heap = [(-c, ch) for ch, c in counts.items()]
    heapq.heapify(heap)

    result = []
    prev = None                         # held (count, letter) from last step
    while heap:
        neg_c, ch = heapq.heappop(heap)  # most frequent letter now
        result.append(ch)
        neg_c += 1                       # used one copy (count closer to zero)
        if prev and prev[0] < 0:         # held letter still has copies
            heapq.heappush(heap, prev)
        prev = (neg_c, ch)               # hold current for next step

    out = "".join(result)
    return out if len(out) == len(s) else ""


print(reorganize("aab") or '""')   # aba
print(reorganize("aaab") or '""')  # ""

aba
""

function reorganize(s) {
  const count = {};
  for (const ch of s) count[ch] = (count[ch] || 0) + 1;

  let result = "";
  let prev = null; // letter placed last step, may not repeat now
  for (let k = 0; k < s.length; k++) {
    let best = null;
    // most frequent letter that is not prev
    for (const ch in count) {
      if (ch === prev) continue;
      if (count[ch] > 0 && (best === null || count[ch] > count[best])) {
        best = ch;
      }
    }
    if (best === null) return ""; // nothing valid to place
    result += best;
    count[best]--;
    prev = best;                  // cannot use this letter next step
  }
  return result;
}

console.log(reorganize("aab") || '""');  // aba
console.log(reorganize("aaab") || '""'); // ""

aba
""

Let us walk through the Python version line by line, because the place-then-hold step is the part people get wrong.

The line counts = Counter(s) counts each letter. Counter is a ready-made counter in Python. For "aab" it gives a is 2 and b is 1.

The next two lines build the heap. We write (-c, ch) so the count is negative. Python’s heapq is a min-heap. A min-heap gives the smallest first. The smallest negative is the largest real count. So the most frequent letter sits on top. heapify turns the list into a valid heap in one pass.

The line prev = None is the held slot. It holds the letter we just placed. We cannot place it again on the very next step.

Inside the loop, heappop(heap) gives the most frequent letter right now. We append ch to the result. Then neg_c += 1 reduces the count by one. Remember the count is negative, so adding one moves it toward zero. That means one copy used.

The line if prev and prev[0] < 0: checks the held letter. If it still has copies left, push it back into the heap now. We delayed it by exactly one step. So it cannot land next to itself. Then prev = (neg_c, ch) holds the current letter for the next step.

At the end, if the result is shorter than the input, some letter could not be placed. So we return "".

⏱️ Time and Space Complexity

The brute force tries permutations, so it is factorial time and useless for real input. The heap version pushes and pops each letter copy once. Each heap step costs O(log k), where k is the number of distinct letters. With n letters total, the work is O(n log k). The space is O(k) for the heap, which is at most 26 for lowercase letters.

🧩 Key Takeaways

• ✅ Place the most frequent letter first, because it is the hardest to fit.
• ✅ A max-heap always hands you the most frequent remaining letter.
• ✅ Hold the letter you just used for one step so it never lands twice in a row.
• ✅ Push the held letter back only after you place a different letter.
• ✅ If one letter appears more than (n + 1) / 2 times, the arrangement is impossible.

🚀 What’s Next?

• Design Twitter
• Maximum Profit in Job Scheduling