AlgoMaster Logo

Reorganize String

mediumFrequency8 min readUpdated June 23, 2026

Understanding the Problem

We need to rearrange the characters of a string so that no two identical characters sit next to each other. If that is not possible, we return an empty string.

When is it impossible? Consider the string "aaab". It has three as and one b. Even placing b between two as gives "aaba", which still has adjacent as. There are not enough non-a characters to separate all the as.

This generalizes to a single condition: if any character appears more than (n + 1) / 2 times (where n is the string length), no valid arrangement exists. The reason is that a valid arrangement places copies of any character at least two positions apart. In a string of length n, the most positions you can use with that spacing is ceil(n / 2), which equals (n + 1) / 2. A character whose count exceeds that must be placed in two adjacent positions somewhere, which violates the constraint.

Key Constraints:

  • 1 <= s.length <= 500 → n is small, so an O(n) solution is easy to reach and there is no overflow concern with int counts.
  • s consists of lowercase English letters → Only 26 distinct characters, so a fixed-size frequency array of length 26 replaces a hash map.

Approach 1: Sorting by Frequency

Intuition

To spread characters apart, place the most frequent characters first, since they are the hardest to separate.

Sort all characters by frequency in descending order, then fill them into a result array at even indices first (0, 2, 4, ...). Once the even indices run out, continue at odd indices (1, 3, 5, ...). Two characters written consecutively in this order land at positions that differ by 2 (or by 1 only at the even-to-odd wrap), so identical copies never end up adjacent. Processing from most frequent to least frequent puts the dominant character into the well-separated even positions, and the remaining characters fill the gaps.

Before filling, check the impossibility condition: if any character appears more than (n + 1) / 2 times, return "".

Algorithm

  1. Count the frequency of each character in the string.
  2. Check if any frequency exceeds (n + 1) / 2. If so, return "".
  3. Create a list of characters sorted by frequency in descending order. Each character appears as many times as its frequency.
  4. Fill the result array: place characters at indices 0, 2, 4, ..., then 1, 3, 5, ...
  5. Return the result as a string.

Example Walkthrough

result
1Frequencies: a=3, b=2, c=1. Sorted: [a, a, a, b, b, c]. Start filling at idx=0.
0
idx
1
2
3
4
5
1/7

Code

This approach pre-sorts once and then fills positions. The next approach builds the string one character at a time, repeatedly selecting the most frequent character that differs from the one just placed. A max heap keeps the selection efficient, and the same greedy idea generalizes to cases where the gap between repeats must be larger than one.

Approach 2: Max Heap (Greedy)

Intuition

This approach builds the string one character at a time. At each position, place the character with the highest remaining frequency, subject to the rule that it cannot equal the character just placed. Spending the most common character whenever it is allowed prevents being left with too many copies of one character at the end, when no other characters remain to separate them.

To enforce the "different from the previous character" rule with a heap, hold the just-placed character aside for one round instead of pushing it back immediately. On the next iteration, push it back (with its count decremented) before popping the next character. Because it is absent from the heap during the pop, it cannot be selected for the adjacent position.

Algorithm

  1. Count the frequency of each character.
  2. Check if any frequency exceeds (n + 1) / 2. If so, return "".
  3. Build a max heap with entries (frequency, character).
  4. Initialize prev as null (no previous character yet).
  5. While the heap is not empty:
    • Pop the character with the highest frequency.
    • Append it to the result.
    • If prev still has remaining count, push it back into the heap.
    • Set prev to the current character (with decremented count).
  6. Return the result.

Example Walkthrough

result
1Heap: [(3,a), (2,b), (1,c)]. prev = null.
0
pos
1
2
3
4
5
maxHeap
1Heap: [(3,a), (2,b), (1,c)]
(3,a)(2,b)(1,c)
1/7

Code

The heap approach generalizes well, but for this problem it maintains a heap over at most 26 characters when only the single most frequent character drives the placement. The next approach drops both the sort and the heap: count frequencies, then fill indices directly in one linear pass.

Approach 3: Frequency Count + Index Filling (Optimal)

Intuition

The result array has positions 0 through n-1. Fill positions 0, 2, 4, ... first, then 1, 3, 5, ... Characters written one after another in this order land at indices that differ by 2, except at the single wrap from the last even index to index 1. Indices 2 apart are never adjacent, so a character only risks being next to itself at that wrap point.

The strategy:

  1. Find the most frequent character.
  2. Place all of its copies at even indices first, since it needs the most separation.
  3. Place every remaining character in the remaining slots, continuing the even-then-odd order.

This works as long as the most frequent character's count does not exceed (n + 1) / 2.

Algorithm

  1. Count the frequency of each character.
  2. Find the character with the maximum frequency.
  3. If max frequency exceeds (n + 1) / 2, return "".
  4. Place the most frequent character at indices 0, 2, 4, ... until its count is exhausted.
  5. Continue placing remaining characters at the current index, wrapping from even to odd indices when even indices are filled.
  6. Return the result.

Example Walkthrough

result
1Frequencies: a=3, b=2, c=1. Max freq char = 'a' (3). (6+1)/2 = 3. Valid.
0
idx
1
2
3
4
5
1/7

Code