"""
p87 — Reorganize String (LC 767)

INVARIANT (feasibility): possible iff max_freq <= (n + 1) // 2. Pigeonhole tight.

INVARIANT (heap + cooldown): after placing letter L, hold L in a buffer for
  exactly one turn. The heap holds available letters by max count.
"""
from __future__ import annotations

import heapq
import random
from collections import Counter
from itertools import permutations


def reorganize_string_heap(s: str) -> str:
    """Max-heap with 1-step cooldown buffer. O(n log k)."""
    if not s:
        return ""
    counts = Counter(s)
    n = len(s)
    if max(counts.values()) > (n + 1) // 2:
        return ""

    heap = [(-cnt, ch) for ch, cnt in counts.items()]
    heapq.heapify(heap)
    out: list[str] = []
    buffered: tuple[int, str] | None = None  # (neg_count, char) waiting one turn
    while heap:
        neg_cnt, ch = heapq.heappop(heap)
        out.append(ch)
        new_neg = neg_cnt + 1  # used one
        # Push the previously-buffered letter back (its 1-turn cooldown is up).
        if buffered is not None and buffered[0] < 0:
            heapq.heappush(heap, buffered)
        # Now buffer the current letter (delay its return by one turn).
        buffered = (new_neg, ch) if new_neg < 0 else None
    return "".join(out)


def reorganize_string_even_index(s: str) -> str:
    """Fill even indices first with most frequent, then odd. O(n + k log k)."""
    n = len(s)
    if not s:
        return ""
    counts = Counter(s)
    max_freq = max(counts.values())
    if max_freq > (n + 1) // 2:
        return ""

    # Most-frequent first ensures even-index packing covers the heavy hitter.
    sorted_chars = sorted(counts.items(), key=lambda x: -x[1])

    out = [""] * n
    idx = 0  # start at even positions
    for ch, cnt in sorted_chars:
        for _ in range(cnt):
            if idx >= n:
                idx = 1  # switch to odd positions
            out[idx] = ch
            idx += 2
    return "".join(out)


def reorganize_string_brute(s: str) -> str:
    """Oracle: enumerate permutations; return first valid. Small inputs only."""
    seen = set()
    for perm in permutations(s):
        if perm in seen:
            continue
        seen.add(perm)
        if all(perm[i] != perm[i + 1] for i in range(len(perm) - 1)):
            return "".join(perm)
    return ""


def _is_valid(orig: str, result: str) -> bool:
    if result == "":
        # Infeasible: check feasibility.
        return max(Counter(orig).values(), default=0) > (len(orig) + 1) // 2
    if Counter(result) != Counter(orig):
        return False
    return all(result[i] != result[i + 1] for i in range(len(result) - 1))


def edge_cases() -> None:
    assert _is_valid("aab", reorganize_string_heap("aab"))
    assert _is_valid("aaab", reorganize_string_heap("aaab"))  # infeasible
    assert reorganize_string_heap("aaab") == ""

    assert _is_valid("aab", reorganize_string_even_index("aab"))
    assert reorganize_string_even_index("aaab") == ""

    # Single char.
    assert reorganize_string_heap("a") == "a"
    # Empty.
    assert reorganize_string_heap("") == ""

    # Exact feasibility threshold: n=5, max=3.
    assert _is_valid("aaabb", reorganize_string_heap("aaabb"))
    assert _is_valid("aaabb", reorganize_string_even_index("aaabb"))


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(300):
        n = rng.randint(1, 7)
        s = "".join(chr(ord("a") + rng.randint(0, 3)) for _ in range(n))

        heap_ans = reorganize_string_heap(s)
        even_ans = reorganize_string_even_index(s)
        brute = reorganize_string_brute(s)

        assert _is_valid(s, heap_ans), (s, heap_ans)
        assert _is_valid(s, even_ans), (s, even_ans)

        # Both empty or both non-empty (feasibility match).
        assert (heap_ans == "") == (brute == ""), (s, heap_ans, brute)
        assert (even_ans == "") == (brute == ""), (s, even_ans, brute)


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")