← Amazon questions

Rearrange string

Filed under Amazon · Also reported at OYO

Free read 2 of 3

The 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

  1. Count occurrences of each character.

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.