Rearrange string
Filed under Amazon · Also reported at OYO
Free read 2 of 3The question
Given a string, rearrange its characters such that no two adjacent characters are the same. If impossible, return an empty string.
Constraints
- String length <= 500.
- Characters are lowercase English letters.
- Return any valid arrangement.
Examples
- Input
- aab
- Output
- aba
- Why
- No two 'a's are adjacent.
Approach
Count occurrences of each character.
Use a max-heap to store characters by frequency.
Always pick the most frequent character that is not the same as the previous one.
Tips
- What they are testing: Test with strings where one character appears more than (n+1)/2 times.
- Common mistake: Using a greedy approach without considering character frequency.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.