Greedy Window Expansion (Expanding Range While Valid) — பேராவல் விரிவு

பேராவல் விரிவு — சாளரம் செல்லும் வரை R நீட்டி; தேவையில் மட்டும் L சுருக்கு — “முடிந்த வரை எடு”.

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

டிரக் ஏற்றம் — கொள்ளளவு வரை அடுத்த பொதி. ஓட்ட சோதனைக் கொடி — பிழை விகிதம் வரை விரிவு.

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

செல்லும்வரை R++; செல்லாதபோது L++. அதிகநீளம் வினாவில் மிக நீண்ட செல்லும் சாளரம்.

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

def longest_unique_substring(s: str) -> int:
    seen, L, best = {}, 0, 0
    for R, ch in enumerate(s):
        if ch in seen and seen[ch] >= L:
            L = seen[ch] + 1
        seen[ch] = R
        best = max(best, R - L + 1)
    return best


print(longest_unique_substring("abcabcbb"))

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

• உகந்த சாளரம் உள்ளூர் விரிவில் கிடைக்காது — எதிர் உதாரணம்.
• பல சுருக்கப் படிகள் தேவையில் L தடை.

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

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