Minimum Window Tracking (Finding Smallest Valid Window) — சிறிய செல்லும் சாளரம்

சிறிய சாளரம் — நிபந்தனை நிறைவுடைய குறுகிய தொடர்; விரித்து பின் சுருக்கி சிறந்ததை பதிவு.

உண்மை உலகில் இது ஏன் முக்கியம்?

சிறிய திருத்தத் தொகுதி — அனைத்து சோதனைகளும் பச்சை; சட்ட பிரிவுகள் — குறைந்தபட்ச உரை; புள்ளிவிவர மாதிரி — அனைத்து வகுப்புகளும்.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

“தேவை/உள்ளது” எண்ணி வரைபடம். R விரி நிறைவு வரை; பின் நிறைவுடன் L நகர்த்தி சிறப்பு; பதிவு; மீண்டும் R.

Pythonில் முயற்சி செய்வோம்

from collections import Counter


def min_window(s: str, t: str) -> str:
    need = Counter(t)
    required = len(need)
    formed = 0
    wc: dict[str, int] = {}
    L, best = 0, (10**9, 0, 0)

    for R, ch in enumerate(s):
        wc[ch] = wc.get(ch, 0) + 1
        if ch in need and wc[ch] == need[ch]:
            formed += 1
        while formed == required:
            if R - L + 1 < best[0]:
                best = (R - L + 1, L, R)
            left = s[L]
            wc[left] -= 1
            if left in need and wc[left] < need[left]:
                formed -= 1
            L += 1

    return "" if best[0] > len(s) else s[best[1] : best[2] + 1]


print(min_window("ADOBECODEBANC", "ABC"))

அடிக்கடி நேரும் தவறுகள்

• முழு சுருக்கத்திற்கு முன் best.
• L நகர்வில் “have” மறைப்பு.
• நிறைவு சோதனை O(1) — நிறைவு எண்ணி.

முக்கியச் சுருக்கக் குறிப்புகள்

• உட்கூறு மூடு வினாக்கள் வார்ப்புரு.
• need/formed எண்ணிகள்.