"""
p02 — Valid Parentheses
=======================
LeetCode 20 · Easy · Topics: String, Stack
Companies: Amazon, Microsoft, Salesforce, Bloomberg
"""

import random
from typing import List


# ----------------------------------------------------------------------
# 1. BRUTE FORCE — repeatedly remove adjacent matched pairs. O(N^2).
# ----------------------------------------------------------------------
def is_valid_brute(s: str) -> bool:
    prev = None
    while prev != s:
        prev = s
        s = s.replace("()", "").replace("[]", "").replace("{}", "")
    return s == ""


# ----------------------------------------------------------------------
# 2. OPTIMAL — single-pass stack with closer→opener lookup. O(N) time, O(N) space.
# ----------------------------------------------------------------------
_PAIRS = {")": "(", "]": "[", "}": "{"}
_OPENERS = set("([{")


def is_valid(s: str) -> bool:
    # INVARIANT: `stack` holds every still-unmatched opener in opening order.
    stack: List[str] = []
    for c in s:
        if c in _OPENERS:
            stack.append(c)
        elif c in _PAIRS:
            # Empty check FIRST: a closer on empty stack means no opener exists.
            # Pop AND type-check: the most recent opener must match this closer's type.
            if not stack or stack.pop() != _PAIRS[c]:
                return False
        # Per problem, no other chars. If clarified otherwise, branch here.
    # End check: any unmatched opener remaining → invalid.
    return not stack


# ----------------------------------------------------------------------
# 3. STRESS TEST
# ----------------------------------------------------------------------
def _random_bracket_string(rng: random.Random, max_len: int) -> str:
    n = rng.randint(0, max_len)
    return "".join(rng.choice("()[]{}") for _ in range(n))


def _random_balanced_string(rng: random.Random, max_depth: int) -> str:
    """Generate a guaranteed-balanced string for positive-case coverage."""
    pairs = [("(", ")"), ("[", "]"), ("{", "}")]
    result: List[str] = []
    stack: List[str] = []
    for _ in range(rng.randint(0, max_depth * 2)):
        if stack and rng.random() < 0.5:
            result.append(stack.pop())
        else:
            o, c = rng.choice(pairs)
            result.append(o)
            stack.append(c)
    while stack:
        result.append(stack.pop())
    return "".join(result)


def stress_test(iterations: int = 1000) -> None:
    rng = random.Random(42)
    for it in range(iterations):
        # Mix random strings (mostly invalid) and balanced strings (valid).
        s = _random_balanced_string(rng, 20) if it % 3 == 0 else _random_bracket_string(rng, 25)
        a = is_valid_brute(s)
        b = is_valid(s)
        assert a == b, f"disagreement on {s!r}: brute={a}, optimal={b}"
    print(f"stress_test PASSED — {iterations} iterations")


# ----------------------------------------------------------------------
# 4. EDGE CASES
# ----------------------------------------------------------------------
def edge_cases() -> None:
    cases = [
        ("()[]{}", True, "sequential pairs"),
        ("([{}])", True, "full nesting"),
        ("(]", False, "type mismatch — counter-only solutions FAIL here"),
        ("]", False, "close-first / empty stack"),
        ("((", False, "non-empty stack at end"),
        ("", True, "empty string is valid"),
        ("(" * 1000 + ")" * 1000, True, "deeply nested — iterative must not stack-overflow"),
    ]
    for s, expected, label in cases:
        actual = is_valid(s)
        status = "PASS" if actual == expected else "FAIL"
        display = s if len(s) <= 30 else f"{s[:15]}...({len(s)} chars)"
        print(f"  [{status}] {label}: {display!r} → {actual} (expected {expected})")


if __name__ == "__main__":
    print("=== Edge cases ===")
    edge_cases()
    print("\n=== Stress test ===")
    stress_test()