"""
p45 — Reorganize String (LeetCode 767, MEDIUM).

Two implementations:
    reorganize_string_heap     — max-heap with one-iteration STASH. O(N log Σ).
    reorganize_string_indexed  — counting-sort placement (even-then-odd). O(N + Σ log Σ).

Feasibility: answer exists iff max_count <= (N + 1) // 2.

Brute oracle: permutations (used only for N <= 7).
Stress: 500 random strings; validate output with is_valid (permutation + no adjacent dup),
plus compare-with-brute on small inputs.
"""
from __future__ import annotations
import heapq
import random
from collections import Counter
from itertools import permutations
from typing import Optional


# --------------------------------------------------------------------------------------
# Heap with stash. O(N log Σ).
# INVARIANT: at the top of each iteration, `prev` holds the (count, char) that was
# placed in the previous iteration but NOT YET pushed back into the heap. This makes
# it invisible to the next pop, guaranteeing a different character is chosen.
# --------------------------------------------------------------------------------------
def reorganize_string_heap(s: str) -> str:
    n = len(s)
    cnt = Counter(s)
    if max(cnt.values()) > (n + 1) // 2:
        return ""

    heap = [(-c, ch) for ch, c in cnt.items()]
    heapq.heapify(heap)

    out: list[str] = []
    prev_count, prev_char = 0, ""   # 0 means "nothing stashed"
    while heap:
        c, ch = heapq.heappop(heap)   # c is negative
        out.append(ch)
        # Now push the PREVIOUSLY-stashed char back, if still has count > 0.
        if prev_count < 0:
            heapq.heappush(heap, (prev_count, prev_char))
        # Stash the just-used char for one iteration.
        prev_count, prev_char = c + 1, ch   # c is negative; +1 decrements magnitude

    return "".join(out)


# --------------------------------------------------------------------------------------
# Counting-sort placement. O(N + Σ log Σ). Deterministic.
# INVARIANT: place highest-count char first at indices 0, 2, 4, ...; wrap to 1, 3, 5, ...
# Feasibility check guarantees no collision.
# --------------------------------------------------------------------------------------
def reorganize_string_indexed(s: str) -> str:
    n = len(s)
    cnt = Counter(s)
    if max(cnt.values()) > (n + 1) // 2:
        return ""

    # Sort chars by count desc (ties broken by char for determinism).
    chars = sorted(cnt.keys(), key=lambda c: (-cnt[c], c))

    out = [""] * n
    idx = 0
    for ch in chars:
        for _ in range(cnt[ch]):
            out[idx] = ch
            idx += 2
            if idx >= n:
                idx = 1
    return "".join(out)


# --------------------------------------------------------------------------------------
# Brute oracle: permutations. Use only for N <= 7.
# Returns SOME valid permutation, or "" if none exists.
# --------------------------------------------------------------------------------------
def reorganize_string_brute(s: str) -> str:
    seen: set[str] = set()
    for perm in permutations(s):
        candidate = "".join(perm)
        if candidate in seen:
            continue
        seen.add(candidate)
        if all(candidate[i] != candidate[i + 1] for i in range(len(candidate) - 1)):
            return candidate
    return ""


# --------------------------------------------------------------------------------------
# Validator
# --------------------------------------------------------------------------------------
def is_valid(out: str, original: str) -> bool:
    if Counter(out) != Counter(original):
        return False
    return all(out[i] != out[i + 1] for i in range(len(out) - 1))


# --------------------------------------------------------------------------------------
# Tests
# --------------------------------------------------------------------------------------
def edge_cases() -> None:
    # LC canonical
    out = reorganize_string_heap("aab")
    assert is_valid(out, "aab"), out
    assert reorganize_string_heap("aaab") == ""
    assert reorganize_string_indexed("aaab") == ""

    # Single character
    assert reorganize_string_heap("a") == "a"
    assert reorganize_string_indexed("a") == "a"

    # All same
    assert reorganize_string_heap("aaaa") == ""

    # Tight feasibility: n=5, max=3 -> (5+1)//2 = 3, OK
    out = reorganize_string_heap("aaabb")
    assert is_valid(out, "aaabb"), out
    out = reorganize_string_indexed("aaabb")
    assert is_valid(out, "aaabb"), out

    # n=6, max=3 -> (6+1)//2=3, OK
    out = reorganize_string_heap("aaabbc")
    assert is_valid(out, "aaabbc"), out

    # n=4, max=3 -> 3 > 2, impossible
    assert reorganize_string_heap("aaab") == ""

    # Two distinct, balanced
    out = reorganize_string_heap("ab")
    assert is_valid(out, "ab"), out

    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)

    # Part 1: small N -- compare with brute oracle on FEASIBILITY (existence only).
    # Both produce SOME valid output if one exists, "" otherwise.
    for _ in range(200):
        n = rng.randint(1, 7)
        alphabet = "abc"
        s = "".join(rng.choice(alphabet) for _ in range(n))
        h = reorganize_string_heap(s)
        i = reorganize_string_indexed(s)
        b = reorganize_string_brute(s)

        # Existence agreement
        assert (h == "") == (b == ""), f"heap feasibility mismatch: s={s} h={h!r} b={b!r}"
        assert (i == "") == (b == ""), f"indexed feasibility mismatch: s={s} i={i!r} b={b!r}"

        # When non-empty, validate output
        if h:
            assert is_valid(h, s), f"heap invalid: s={s} h={h}"
        if i:
            assert is_valid(i, s), f"indexed invalid: s={s} i={i}"

    # Part 2: larger N -- just validate outputs (no brute).
    for _ in range(300):
        n = rng.randint(10, 100)
        alphabet = "abcde"
        s = "".join(rng.choice(alphabet) for _ in range(n))
        h = reorganize_string_heap(s)
        i = reorganize_string_indexed(s)

        # Both must agree on feasibility.
        assert (h == "") == (i == ""), f"feasibility mismatch on s={s}"
        if h:
            assert is_valid(h, s), f"heap invalid: s={s} h={h}"
        if i:
            assert is_valid(i, s), f"indexed invalid: s={s} i={i}"

    print("stress_test: 200 small (brute oracle) + 300 medium random strings — all valid.")


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