Rearrange a String So Adjacent Characters Differ
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Rearrange the characters of a lowercase string so that no two adjacent
characters are equal. Return the lexicographically smallest valid rearrangement,
or an empty string if no valid rearrangement exists.
### Constraints & Assumptions
- The string length is between 1 and 200,000.
- The input contains lowercase English letters.
- Every input character must appear exactly once in a non-empty result.
- The lexicographic rule makes the output deterministic even when many arrangements are valid.
### Clarifications
- Character counts, not original positions, determine feasibility.
- The same character may reappear after at least one different character.
- Return an empty string only when no arrangement can satisfy the adjacency rule.
### Examples
```text
s = "aab" -> "aba"
s = "aaab" -> ""
s = "vvvlo" -> "vlvov"
```
### Hints
```hint Check feasibility
Compare the largest character frequency with the number of positions available to separate its copies.
```
```hint Choose safely and deterministically
At each position, try available characters in order but avoid a choice that makes the remaining counts impossible.
```
Overview: Construct the lexicographically smallest rearrangement of a lowercase string with no equal adjacent characters, checking feasibility after each deterministic choice and returning empty when separation is impossible.
Read the full Amazon Software Engineer interview experience this question came from
Rearrange all characters of a lowercase string so that no two adjacent characters are equal. Return the lexicographically smallest valid rearrangement, or an empty string if no valid rearrangement exists. Every input character must appear exactly once in a nonempty result; character counts, not original positions, determine feasibility, and a character may reappear after at least one different character.
Constraints
- 1 <= len(s) <= 200000.
- The input contains only lowercase English letters.
- Every input character must appear exactly once in a nonempty result.
- Return an empty string only when no arrangement can avoid equal adjacent characters.
- Among valid arrangements, return the lexicographically smallest one.
Examples
Input: ('aab',)
Expected Output: 'aba'
Explanation: This source example has one feasible arrangement, which is therefore lexicographically smallest.
Input: ('aaab',)
Expected Output: ''
Explanation: Three copies of a cannot be separated by the one other character.
Hints
- First compare the largest frequency with the number of separator positions available.
- At each position, try letters in order but reject a choice if the remaining dominant count can no longer be separated, including from the letter just chosen.