"""
p30 — Minimum Window Substring (LeetCode 76).

Three implementations:
    min_window         — canonical O(N+M) with match counter
    min_window_naive   — O(N*sigma), validity via Counter scan each shrink
    min_window_brute   — O(N^2 * M), try every (i,j), ORACLE

Run: python3 solution.py
"""
from __future__ import annotations
import random
from collections import Counter, defaultdict


# --------------------------------------------------------------------------------------
# Canonical: match counter. O(N + M).
# --------------------------------------------------------------------------------------
def min_window(s: str, t: str) -> str:
    if not t or not s or len(t) > len(s):
        return ""
    need = Counter(t)
    required = len(need)
    have: dict[str, int] = defaultdict(int)
    # INVARIANT: formed = number of distinct chars c in `need` with have[c] >= need[c].
    formed = 0
    best_len = float("inf")
    best_l = 0
    left = 0
    for right, c in enumerate(s):
        have[c] += 1
        # Exactly == (not >=): increment formed only at the moment we first meet the need.
        if c in need and have[c] == need[c]:
            formed += 1
        # Window is valid; contract from left while it stays valid.
        while formed == required:
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_l = left
            lc = s[left]
            # Check BEFORE decrement: if we're about to fall below need, we lose a match.
            if lc in need and have[lc] == need[lc]:
                formed -= 1
            have[lc] -= 1
            left += 1
    return "" if best_len == float("inf") else s[best_l : best_l + int(best_len)]


# --------------------------------------------------------------------------------------
# Naive: same template, but validity via dict scan each step. O(N * sigma).
# --------------------------------------------------------------------------------------
def min_window_naive(s: str, t: str) -> str:
    if not t or not s or len(t) > len(s):
        return ""
    need = Counter(t)
    have: dict[str, int] = defaultdict(int)

    def valid() -> bool:
        for k, v in need.items():
            if have[k] < v:
                return False
        return True

    best_len = float("inf")
    best_l = 0
    left = 0
    for right, c in enumerate(s):
        have[c] += 1
        while valid():
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_l = left
            have[s[left]] -= 1
            left += 1
    return "" if best_len == float("inf") else s[best_l : best_l + int(best_len)]


# --------------------------------------------------------------------------------------
# Brute oracle: try every (i, j), Counter-compare. O(N^2 * M).
# --------------------------------------------------------------------------------------
def min_window_brute(s: str, t: str) -> str:
    if not t or not s or len(t) > len(s):
        return ""
    n = len(s)
    need = Counter(t)
    best_len = n + 1
    best_l = 0
    for i in range(n):
        window: dict[str, int] = defaultdict(int)
        for j in range(i, n):
            window[s[j]] += 1
            # Check if window covers need.
            ok = True
            for k, v in need.items():
                if window[k] < v:
                    ok = False
                    break
            if ok:
                if j - i + 1 < best_len:
                    best_len = j - i + 1
                    best_l = i
                break  # extending j further only makes window longer
    return "" if best_len == n + 1 else s[best_l : best_l + best_len]


# --------------------------------------------------------------------------------------
# Tests
# --------------------------------------------------------------------------------------
def edge_cases() -> None:
    # (s, t, expected_length); we compare lengths because tied windows are all valid.
    cases = [
        ("ADOBECODEBANC", "ABC", 4),         # "BANC"
        ("a", "a", 1),
        ("a", "aa", 0),                       # no window
        ("aa", "aa", 2),
        ("ab", "b", 1),
        ("bba", "ab", 2),                     # "ba"
        ("", "a", 0),
        ("a", "", 0),
        ("ADOBECODEBANC", "AABC", 6),         # "ADOBEC...BANC" → smallest is "ADOBECODEBA"? need 2 A's → "DOBECODEBA" length 10? Check.
        ("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
         "AAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"
         "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"
         "BBBBBBBBBB", "AB", 2),
    ]
    for s, t, _expected_len in cases:
        a = min_window(s, t)
        b = min_window_naive(s, t)
        c = min_window_brute(s, t)
        # Compare LENGTHS; any tied window is acceptable.
        assert len(a) == len(b) == len(c), (
            f"DISAGREE on (s,t)=({s!r},{t!r}): canonical={a!r} naive={b!r} brute={c!r}"
        )
        # Each non-empty result must actually be a valid window.
        for impl, w in [("canonical", a), ("naive", b), ("brute", c)]:
            if w:
                window_counter = Counter(w)
                need_counter = Counter(t)
                for k, v in need_counter.items():
                    assert window_counter[k] >= v, (
                        f"{impl} returned {w!r} for t={t!r} but missing char {k!r}"
                    )
    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    alphabet = "abcde"
    for _ in range(200):
        n = rng.randint(0, 25)
        m = rng.randint(0, 8)
        s = "".join(rng.choice(alphabet) for _ in range(n))
        t = "".join(rng.choice(alphabet) for _ in range(m))
        a = min_window(s, t)
        b = min_window_naive(s, t)
        c = min_window_brute(s, t)
        assert len(a) == len(b) == len(c), (
            f"DISAGREE: s={s!r} t={t!r} canonical={a!r} naive={b!r} brute={c!r}"
        )
    print("stress_test: 200 random (s,t) pairs — all three agree on window length.")


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