"""
p29 — Longest Substring Without Repeating Characters (LeetCode 3).

Three implementations:
    length_of_longest_substring_map    — O(N), char -> last_index map (CANONICAL)
    length_of_longest_substring_set    — O(N) amortized, set + shrinking left
    length_of_longest_substring_brute  — O(N^2 * sigma), all substrings, ORACLE

Run: python3 solution.py
"""
from __future__ import annotations
import random


# --------------------------------------------------------------------------------------
# Canonical: char -> last seen index, jump left with max() guard.
# --------------------------------------------------------------------------------------
def length_of_longest_substring_map(s: str) -> int:
    last_seen: dict[str, int] = {}
    left = 0
    best = 0
    # INVARIANT: s[left..right] has all-unique characters at end of each iteration.
    for right, c in enumerate(s):
        if c in last_seen and last_seen[c] >= left:
            # CRITICAL: max() not bare assign. On "abba", when right=3, c='a',
            # last_seen['a']=0 but left=2; we must NOT jump backward to 1.
            left = last_seen[c] + 1
        last_seen[c] = right
        best = max(best, right - left + 1)
    return best


# --------------------------------------------------------------------------------------
# Alternative: set + shrinking pointer. Self-documenting; left advances monotonically.
# --------------------------------------------------------------------------------------
def length_of_longest_substring_set(s: str) -> int:
    seen: set[str] = set()
    left = 0
    best = 0
    for right, c in enumerate(s):
        while c in seen:
            seen.discard(s[left])
            left += 1
        seen.add(c)
        best = max(best, right - left + 1)
    return best


# --------------------------------------------------------------------------------------
# Brute oracle: try every substring, check uniqueness via set.
# --------------------------------------------------------------------------------------
def length_of_longest_substring_brute(s: str) -> int:
    n = len(s)
    best = 0
    for i in range(n):
        seen: set[str] = set()
        for j in range(i, n):
            if s[j] in seen:
                break
            seen.add(s[j])
            if j - i + 1 > best:
                best = j - i + 1
    return best


# --------------------------------------------------------------------------------------
# Tests
# --------------------------------------------------------------------------------------
def edge_cases() -> None:
    cases = [
        ("", 0),
        (" ", 1),
        ("a", 1),
        ("bbbbb", 1),
        ("abcdef", 6),
        ("abcabcbb", 3),
        ("pwwkew", 3),
        ("dvdf", 3),          # left must not jump backward
        ("abba", 2),          # left must not jump backward (the killer)
        ("tmmzuxt", 5),       # "mzuxt"
        ("aab", 2),
        ("au", 2),
        ("aabaab!bb", 3),
    ]
    for s, expected in cases:
        for name, fn in [
            ("map", length_of_longest_substring_map),
            ("set", length_of_longest_substring_set),
            ("brute", length_of_longest_substring_brute),
        ]:
            got = fn(s)
            assert got == expected, f"{name}({s!r}) → {got}, expected {expected}"
    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    alphabet = "abcd"
    for _ in range(300):
        n = rng.randint(0, 20)
        s = "".join(rng.choice(alphabet) for _ in range(n))
        a = length_of_longest_substring_map(s)
        b = length_of_longest_substring_set(s)
        c = length_of_longest_substring_brute(s)
        assert a == b == c, f"DISAGREE on {s!r}: map={a} set={b} brute={c}"
    print("stress_test: 300 random strings — all three implementations agree.")


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