Reorganize String
Asked at Amazon
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | MEDIUM | View all Amazon questions → |
How to Think About It
Count the frequency of each character using a hash map.
If the most frequent character appears more than (n+1)/2 times, return empty string.
Use a max-heap to always pick the two most frequent characters and alternate them.
Alternatively, place the most frequent character at even indices first, then odd indices.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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)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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Reorganize String?
Reorganize String is asked at Amazon. 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.