Katkat
Back

Rearrange a String So Adjacent Characters Differ

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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

s = "aab" -> "aba"
s = "aaab" -> ""
s = "vvvlo" -> "vlvov"

Hints

Hints

Hint 1

Check feasibility: Compare the largest character frequency with the number of positions available to separate its copies.

Hint 2

Choose safely and deterministically: At each position, try available characters in order but avoid a choice that makes the remaining counts impossible.