Reorganize String

Intuition

A valid arrangement exists exactly when no character appears more than ceil(n / 2) times, because that character can occupy at most every other position. Once that check passes, we can build the answer deterministically. Filling positions 0, 2, 4, ... with the most frequent character and continuing with the remaining characters guarantees that any two equal characters land at least two indices apart. When the even indices run out we wrap to index 1 and keep stepping by two through the odd indices. Because we always advance by two, adjacent cells are populated from different runs and never match.

Algorithm walkthrough

1. 1Count the frequency of each character and identify the most frequent one.
2. 2If that maximum frequency exceeds (n + 1) / 2, return an empty string because separation is impossible.
3. 3Create a result buffer and start an index at 0, stepping by two through the even positions.
4. 4Place every copy of the most frequent character first, then continue with the remaining characters.
5. 5When the index passes the end of the buffer, reset it to 1 so it walks the odd positions.
6. 6Join the buffer and return it; equal characters are guaranteed to be two positions apart.

Implementation

from collections import Counter

class Solution:
    def reorganizeString(self, s: str) -> str:
        counts = Counter(s)
        n = len(s)
        max_char, max_freq = counts.most_common(1)[0]
        if max_freq > (n + 1) // 2:
            return ""
        result = [""] * n
        idx = 0
        for ch, cnt in counts.most_common():
            for _ in range(cnt):
                if idx >= n:
                    idx = 1
                result[idx] = ch
                idx += 2
        return "".join(result)