Reorganize String

1. Count Character Frequencies

• Build a frequency map for every character in the string
• For example, "aab" gives { a: 2, b: 1 }

2. Check for Impossibility

• If any single character appears more than Math.ceil(s.length / 2) times, it is impossible to arrange the string without adjacent duplicates
• This is because even in the best case (placing that character at every other position), there are only ceil(n/2) non-adjacent slots available
• If impossible, return ""

3. Sort Characters by Frequency

• Create an array of all characters (with repetitions) and sort them by descending frequency, breaking ties alphabetically
• This ensures the most frequent characters are placed first, filling the even-indexed positions where they have the most room

4. Interleave into Result Array

• Fill positions in order: even indices first (0, 2, 4, ...), then odd indices (1, 3, 5, ...)
• Start at index 0, advance by 2 each step; when the index exceeds the array length, wrap to index 1 and continue filling odd positions
• Since the most frequent character fills the early even slots and the condition in step 2 guarantees it fits, no two adjacent positions will have the same character

5. Return the Result

• Join the result array into a string and return it

Key Insight

The greedy interleaving strategy works because placing the most frequent character at every other position (even indices) guarantees separation. The impossibility check freq > ceil(n/2) is both necessary and sufficient.

• Time: O(n) — counting frequencies is O(n), sorting is bounded by 26 distinct characters making it effectively O(n)
• Space: O(n) — for the result array and sorted characters array