Compile Ready
Module 5 · String Greedy

Reorganize String

MediumProblem 15 of 21 8 min read ~20 min to solve LeetCode
GreedyStringCountingHeapConstruction
Asked atAmazonGoogleMicrosoftMetaOracle

Problem Statement

Given a lowercase string s, rearrange its characters so that no two adjacent characters are the same. Return any valid rearrangement, or return an empty string if no such rearrangement exists.

Input

A lowercase string s.

Output

Any rearranged string with no equal adjacent characters, or an empty string when no valid rearrangement exists.

Constraints

  • •1 <= s.length <= 500
  • •s consists of lowercase English letters

Examples

Example 1

Input: 
s = aab
Output: aba
Explanation: The two a characters are separated by b, so no adjacent characters match.

Example 2

Input: 
s = aaab
Output: empty string
Explanation: The character a appears 3 times in a string of length 4, but only 2 separated slots are available, so a valid arrangement is impossible.

Example 3

Input: 
s = aaabbc
Output: ababac
Explanation: One valid construction places the most frequent character a in even positions first, then fills the remaining gaps with b and c.

Learning Objectives

  • Detect the frequency threshold that makes adjacent separation impossible.
  • Use the most frequent character as the limiting resource in a constructive greedy proof.
  • Implement the count and even-then-odd placement technique in linear time.
  • Relate the array-fill construction to the max-heap strategy of always choosing a different most frequent character.

Intuition

Greedy Insight: The only way to fail is for one character to be too frequent to separate from itself. In a string of length n, a character can occupy at most ceil(n / 2) non-adjacent slots. If the maximum count is larger, return an empty string.

When the maximum count is feasible, place that most frequent character into even indices first: 0, 2, 4, .... This spreads the hardest character as far apart as possible. Then fill the remaining even slots and odd slots with the other characters. This count-and-fill construction is the array version of always choosing a most frequent remaining character that differs from the previous one.

Common mistakes

  • ×Checking the impossibility condition as **maxCount > n / 2**, which rejects valid odd-length cases like aaabb.
  • ×Filling positions from left to right without separating the most frequent character first.
  • ×Returning a sorted string, which clusters identical letters and often violates adjacency.
  • ×Forgetting that any valid rearrangement is acceptable, not necessarily the lexicographically smallest one.

Algorithm Explanation

Greedy strategy Count character frequencies. If the largest frequency exceeds (n + 1) / 2, no arrangement can separate that character. Otherwise, place the most frequent character at even indices first, then place all remaining characters into the next available even indices and finally odd indices.

Why it works Even indices are mutually non-adjacent. They provide exactly ceil(n / 2) slots, the maximum number of copies any one character can safely occupy. By assigning the most constrained character to those separated slots first, the rest of the characters can fill gaps without forcing equal neighbours.

Proof of correctness If maxCount > ceil(n / 2), pigeonhole principle proves impossibility: more copies exist than non-adjacent slots. Otherwise, consider any valid arrangement. The most frequent character can be exchanged into the even slots used by the greedy construction because those slots are pairwise separated and there are enough of them. This exchange does not create equal adjacent copies of that character. After those placements, every remaining empty slot is adjacent only to separated maximum-character slots or to positions filled later by lower-frequency characters. Filling the remaining characters in count order preserves feasibility because no remaining character has more copies than the gaps can absorb. Thus the greedy construction produces a valid arrangement whenever one exists.

Algorithm

  1. Count all characters and find the character with maximum frequency.
  2. If the maximum frequency is greater than (n + 1) / 2, return an empty string.
  3. Create a result character array of length n.
  4. Place all copies of the maximum-frequency character at indices 0, 2, 4, ....
  5. For every other character, continue placing copies at the current index, jumping by 2 each time.
  6. When the index passes the end of the array, reset it to 1 and continue filling odd positions.
  7. Return the completed string.

Solutions

Solution: Count and fill even then odd positions

The most frequent character is the bottleneck. Place it first into the separated even positions, then fill all remaining positions with the other characters. The feasibility check guarantees the first character fits without adjacency and the remaining characters can occupy the gaps.

Step-by-step

  1. Count the 26 lowercase characters and identify the character with the largest count.
  2. If that count exceeds (n + 1) / 2, return an empty string because separation is impossible.
  3. Fill a result array by placing the most frequent character at index 0, then 2, then 4, and so on.
  4. Set that character's remaining count to 0.
  5. Place every other character using the same step of 2. When the index moves past the end, wrap to index 1.
  6. Convert the filled character array to a string.
Time

O(n)

Space

O(n)

Counting uses 26 entries and the result array stores the rearranged string.

Java implementation

Loading…

Dry Run

Sample input

s = aaabbc. Counts are a:3, b:2, and c:1. Since 3 <= (6 + 1) / 2, a valid rearrangement exists.

phasecharcount beforepositions fillednext indexpartial result
feasibilitya3Maximum count fits in separated slots0......
place maximuma30, 2, 41a.a.a.
fill remainingb21, 35ababa.
fill remainingc157ababac

The final arrangement ababac has no equal adjacent characters. The key move was placing all three a characters into non-adjacent even slots before filling the gaps.

Interview Tips

Lead with the impossibility condition: no character may appear more than ceil(n / 2) times. Then choose one implementation strategy. The even-odd fill is compact for lowercase strings; the max-heap version is more general and repeatedly chooses the most frequent character that is not equal to the previous output character.

Likely follow-ups

  • How would you implement the same greedy idea with a max heap?
  • What changes if the alphabet is large or not known in advance?
  • How would you rearrange so identical characters are at least distance **k** apart?
  • Can you produce the lexicographically smallest valid rearrangement among all valid answers?

Similar Problems

Task Scheduler
MediumUses the same maximum-frequency bottleneck idea with cooldown slots.
Remove Duplicate Letters
MediumAnother string greedy where counts determine whether a local choice is safe.
Partition Labels
MediumAlso uses character metadata to make one-pass greedy decisions.
Distant Barcodes
MediumThe same rearrangement pattern applied to integer values.
Rearrange String k Distance Apart
HardGeneralises adjacent separation to a cooldown distance.

Key Takeaways

  • The maximum frequency controls whether reorganisation is possible.
  • Even indices provide the largest set of mutually non-adjacent slots.
  • Place the hardest character first, then fill the remaining gaps.
  • The heap approach and the even-odd fill are two views of the same greedy principle: avoid using the previous character while consuming high counts early.
Reusable template: Frequency-constrained construction: verify the most frequent item fits into separated slots, place it first, then fill the remaining gaps without creating adjacent duplicates.