Quick 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.

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

  1. First compare the largest frequency with the number of separator positions available.
  2. 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.

Loading coding console...

Show the approach

Approach

Count the 26 letters. A rearrangement is impossible when the largest count exceeds ceil(n / 2). Otherwise build the answer left to right and try available letters in lexicographic order, excluding the previous letter. After tentatively selecting letter c, the remaining suffix must begin with a letter other than c. For a suffix of length r, this is feasible exactly when c's remaining count is at most floor(r / 2) and every other count is at most ceil(r / 2). The current maximum, its multiplicity, and the second maximum let each tentative choice check these bounds in constant time after one 26-letter scan. Taking the first safe letter preserves at least one completion and is lexicographically optimal at the first position where answers could differ.

Time complexity:
O(26 * n), which is O(n) for the fixed lowercase alphabet.
Space complexity:
O(n) for the result and O(26) auxiliary counting space.