MediumHash TableStringGreedySortingHeapCountingUpdated Sep 2026

767. Reorganize String

Asked at Amazon, DE Shaw

Difficulty

Medium

Time

O(n log k)

Space

O(n + k)

Pattern

Hash Table

Companies

2

Problem

You are given a string s. Rearrange its characters so that no two neighboring characters are the same. You may use every character exactly once, and the order of the characters is up to you.

Return any valid rearrangement. If no arrangement can avoid equal neighbors, return the empty string "".

A quick way to see when it is impossible: if one character appears more than (n + 1) / 2 times (rounded down), it cannot be separated by the other characters, so the answer is "". Otherwise a valid arrangement always exists.

Same letters must not touch

saab012Input "aab": the two 'a' are adjacent, which is notallowedresultaba012Output "aba": the 'b' sits between the two 'a', soevery pair of neighbors differs
We keep all the letters but reorder them so that equal letters are never side by side.

Constraints

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

Examples

Example 1
Inputs = "aab"
Output"aba"
WhyWe have two 'a' and one 'b'. Putting 'b' in the middle separates the two 'a', so no two neighbors are equal.
Example 2
Inputs = "aaab"
Output""
WhyThere are three 'a' and only one 'b'. The 'a' characters must touch each other somewhere, so no valid arrangement exists.

Asked At

2 companies
CompanyDifficulty
AmazonMediumView all Amazon questions →
DE ShawMediumView all DE Shaw questions →

How to Think About It

1

Count the frequency of each character using a hash map.

2

If the most frequent character appears more than (n+1)/2 times, return empty string.

3

Use a max-heap to always pick the two most frequent characters and alternate them.

4

Alternatively, place the most frequent character at even indices first, then odd indices.

5

The greedy approach of interleaving the top two frequencies guarantees a valid result.

Optimal Approach

Count character frequencies. Check if any character exceeds ceil(n/2); if so, return empty. Build the result by repeatedly taking the two most frequent characters and appending them to the result. Decrement their counts and push them back if they still have remaining count. Continue until all characters are placed. This greedy approach ensures no adjacent duplicates. Time is O(n log k) where k is the number of unique characters.

Greedy with a max-heap

heap (count, char)(2,a)(1,b)frontbackStep 1 — counts in a max-heap: 'a' appears 2 times,'b' onceresultab01Step 2 — pop the top two, append 'a' then 'b'; bothdrop to count 0resultaba012Step 3 — only 'a' is left with count 1, so append it;the result is validif max count > (n+1)//2 → return ""else pop two, append, push back leftovers
Always take the two most frequent letters, place them next to each other, then push back what is left.
ComplexityTime O(n log k)Space O(n + k)n is the length of s and k is the number of distinct characters; each of the n placements costs a heap push/pop of O(log k), and we store the result plus the heap.

What Trips People Up in Real Interviews

1

Ask if any valid rearrangement is acceptable (yes).

2

Mention the frequency check impossibility condition early.

3

Compare heap-based and index-interleaving approaches.

4

Discuss why placing most frequent first on even indices works.

5

Talk about time complexity: O(n log n) with heap, O(n) with counting sort.

Solution Code

O(n log k) time
import heapq
from collections import Counter

def reorganizeString(s):
    count = Counter(s)
    n = len(s)
    for c, cnt in count.items():
        if cnt > (n + 1) // 2:
            return ''
    heap = [(-cnt, c) for c, cnt in count.items()]
    heapq.heapify(heap)
    result = []
    while len(heap) >= 2:
        cnt1, c1 = heapq.heappop(heap)
        cnt2, c2 = heapq.heappop(heap)
        result.extend([c1, c2])
        if cnt1 + 1 < 0:
            heapq.heappush(heap, (cnt1 + 1, c1))
        if cnt2 + 1 < 0:
            heapq.heappush(heap, (cnt2 + 1, c2))
    if heap:
        cnt, c = heapq.heappop(heap)
        if -cnt > 1:
            return ''
        result.append(c)
    return ''.join(result)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Reorganize String problem?

Given a string s, rearrange the characters so that no two adjacent characters are the same. Return any valid rearrangement or an empty string if it is not possible.

How do you solve Reorganize String?

The optimal approach runs in O(n log k) time and O(n + k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Reorganize String?

Reorganize String is asked at Amazon, DE Shaw. It is a medium difficulty problem.

What are common mistakes on Reorganize String?
  • Ask if any valid rearrangement is acceptable (yes).
  • Mention the frequency check impossibility condition early.
  • Compare heap-based and index-interleaving approaches.
  • Discuss why placing most frequent first on even indices works.
  • Talk about time complexity: O(n log n) with heap, O(n) with counting sort.