Arrays, Strings & Hashing Questions

from typing import List

def rabin_karp(text: str, pattern: str) -> List[int]:
    if not pattern:
        return list(range(len(text) + 1))
    n, m = len(text), len(pattern)
    if m > n:
        return []

    # Choose base and modulus
    B = 256                    # common for byte/ASCII
    M = 2**61 - 1              # large M reduces collisions; use M a large prime (here a Mersenne-like prime)
    
    def mod_mul(a, b):
        return (a * b) % M

    # Precompute B^(m-1) % M
    power = pow(B, m-1, M)

    # initial hashes
    h_pat = 0
    h_txt = 0
    for i in range(m):
        h_pat = (h_pat * B + ord(pattern[i])) % M
        h_txt = (h_txt * B + ord(text[i])) % M

    results = []
    for i in range(n - m + 1):
        if h_pat == h_txt:
            # verify to handle collision
            if text[i:i+m] == pattern:
                results.append(i)
        if i < n - m:
            # remove leading char, multiply, add next char
            lead = (ord(text[i]) * power) % M
            h_txt = (h_txt - lead) % M
            h_txt = (h_txt * B + ord(text[i + m])) % M

    return results

from collections import Counter

def first_unique_char(s: str) -> int:
    """
    Return index of first non-repeating character in s, or -1 if none.
    O(n) time, O(k) space where k = distinct characters.
    """
    freq = Counter(s)               # pass 1: count frequencies
    for i, ch in enumerate(s):      # pass 2: find first with freq == 1
        if freq[ch] == 1:
            return i
    return -1

def min_window(s: str, t: str) -> str:
    if not t or not s:
        return ""

    from collections import Counter

    need = Counter(t)                # required counts for chars in t
    window = Counter()               # counts in current window
    required = len(need)             # number of unique chars to satisfy
    formed = 0                       # how many unique chars currently satisfied

    l = 0
    min_len = float("inf")
    min_left = 0

    for r, ch in enumerate(s):
        window[ch] += 1
        # If this char now meets the required frequency, increment formed
        if ch in need and window[ch] == need[ch]:
            formed += 1

        # Try to contract while the window is valid
        while l <= r and formed == required:
            # Update best window
            if (r - l + 1) < min_len:
                min_len = r - l + 1
                min_left = l

            # Remove left char from window and move left pointer
            left_char = s[l]
            window[left_char] -= 1
            if left_char in need and window[left_char] < need[left_char]:
                formed -= 1
            l += 1

    return "" if min_len == float("inf") else s[min_left:min_left + min_len]

from collections import Counter
import string

def is_anagram(s: str, t: str, ascii_only: bool = True, case_sensitive: bool = False) -> bool:
    """
    Return True if s and t are anagrams under the given options.
    ascii_only: if True, ignore characters outside ASCII alphanumerics.
    case_sensitive: if False, compare case-insensitively.
    """
    def normalize(x: str) -> str:
        if not case_sensitive:
            x = x.lower()
        if ascii_only:
            allowed = set(string.ascii_letters + string.digits)
            return ''.join(ch for ch in x if ch in allowed)
        return x

    ns, nt = normalize(s), normalize(t)
    # Quick length check
    if len(ns) != len(nt):
        return False

    # Use fixed-size array for ASCII alphanumerics for O(1) space
    if ascii_only:
        counts = [0] * 128  # cover ASCII range
        for ch in ns:
            counts[ord(ch)] += 1
        for ch in nt:
            counts[ord(ch)] -= 1
            if counts[ord(ch)] < 0:
                return False
        return True

    # Fallback: Counter for full unicode support
    return Counter(ns) == Counter(nt)

import hashlib
import math
from typing import List

class CountMinSketch:
    def __init__(self, epsilon: float=0.01, delta: float=1e-3):
        """
        epsilon: desired additive error (total_count * epsilon)
        delta: probability of error > epsilon (failure prob)
        """
        if not (0 < epsilon < 1 and 0 < delta < 1):
            raise ValueError("epsilon and delta must be in (0,1)")
        self.w = math.ceil(math.e / epsilon)          # width
        self.d = math.ceil(math.log(1.0 / delta))     # depth
        self.count = 0
        self.table: List[List[int]] = [[0]*self.w for _ in range(self.d)]
        self.seeds = [str(i).encode() for i in range(self.d)]  # different salts for hashing

    def _hash(self, item: bytes, seed: bytes) -> int:
        # Use SHA256 keyed by seed; convert to integer
        h = hashlib.sha256(seed + item).digest()
        return int.from_bytes(h, 'big')

    def add(self, item, count: int=1):
        b = str(item).encode()
        for i, seed in enumerate(self.seeds):
            idx = self._hash(b, seed) % self.w
            self.table[i][idx] += count
        self.count += count

    def estimate(self, item) -> int:
        b = str(item).encode()
        estimates = []
        for i, seed in enumerate(self.seeds):
            idx = self._hash(b, seed) % self.w
            estimates.append(self.table[i][idx])
        return min(estimates)

    def merge(self, other: "CountMinSketch"):
        # Must have same w, d and same seeds (or at least same hash functions)
        if self.w != other.w or self.d != other.d:
            raise ValueError("Sketch dimensions must match to merge")
        for i in range(self.d):
            for j in range(self.w):
                self.table[i][j] += other.table[i][j]
        self.count += other.count