Sliding Windows and Incremental Validity
آمادگی مصاحبهٔ الگوریتمی با Python
- In 75 minutes, recognize contiguous-range problems with incrementally maintainable state; contrast fixed-size and variable-size windows.
- Define the window boundaries and validity rule before coding; explain when shrinking can restore validity.
- Independently choose the stored state and shrinking rule for Longest Substring Without Repeating Characters.
- Develop the problem from enumerating substrings and checking uniqueness to a Python sliding-window solution using counts.
- Prove that the maintained window is valid after shrinking and that the best valid length is recorded.
- Count total pointer movements to justify expected O(n) time despite a nested shrinking loop; express space using the number of distinct characters.
- Test empty input, all equal characters, all distinct characters, and repeated characters separated by gaps; reject simple sum-based shrinking rules when negative values invalidate monotonicity.
از بازههای پیوسته تا sliding window
```svg
<svg viewBox="0 0 800 600" xmlns="http://www.w3.org/2000/svg"><text x="400" y="30" text-anchor="middle" class="tm-text" font-size="20">Longest Substring Without Repeating Characters</text><text x="400" y="62" text-anchor="middle" class="tm-muted" font-size="16" direction="rtl">فقط طول • ورودی خالی مجاز • بزرگی و کوچکی حروف مهم</text><rect x="290" y="80" width="220" height="52" rx="10" class="tm-soft"/><text x="400" y="114" text-anchor="middle" class="tm-text" font-size="26">a b a</text><text x="400" y="160" text-anchor="middle" class="tm-text2" font-size="17" direction="rtl">substring: پیوسته، بدون رد کردن کاراکتر</text><text x="400" y="198" text-anchor="middle" class="tm-text" font-size="18">Brute Force</text><rect x="100" y="212" width="180" height="64" rx="10" class="tm-soft"/><rect x="310" y="212" width="180" height="64" rx="10" class="tm-green"/><rect x="520" y="212" width="180" height="64" rx="10" class="tm-soft"/><text x="190" y="251" text-anchor="middle" class="tm-text" font-size="22">a, ab, aba</text><text x="400" y="251" text-anchor="middle" class="tm-text" font-size="22">b, ba</text><text x="610" y="251" text-anchor="middle" class="tm-text" font-size="22">a</text><text x="400" y="304" text-anchor="middle" class="tm-text-accent" font-size="17" direction="rtl">فقط aba تکراری است؛ بلندترینها: ab و ba</text><text x="400" y="346" text-anchor="middle" class="tm-text" font-size="19">sliding window</text><rect x="110" y="362" width="250" height="66" rx="10" class="tm-accent"/><text x="235" y="389" text-anchor="middle" class="tm-text" font-size="18" direction="rtl">بازهٔ فعلی</text><text x="235" y="416" text-anchor="middle" class="tm-text" font-size="20">a b</text><path d="M 370 395 H 430" class="tm-line-accent"/><rect x="440" y="362" width="250" height="66" rx="10" class="tm-soft"/><text x="565" y="389" text-anchor="middle" class="tm-text" font-size="18">Hash Map</text><text x="565" y="416" text-anchor="middle" class="tm-text" font-size="20">a: 1, b: 1</text><text x="400" y="457" text-anchor="middle" class="tm-text2" font-size="17" direction="rtl">ورود و خروج یک عضو ← بهروزرسانی تعدادها</text><rect x="100" y="480" width="270" height="92" rx="10" class="tm-gold"/><text x="235" y="505" text-anchor="middle" class="tm-text" font-size="17" direction="rtl">اندازهٔ ثابت: جمع دو عضو</text><text x="235" y="534" text-anchor="middle" class="tm-text" font-size="21">[2, 1], 3 → 2, [1, 3]</text><text x="235" y="559" text-anchor="middle" class="tm-text2" font-size="16" direction="rtl">خروج 2، ورود 3</text><rect x="410" y="480" width="290" height="92" rx="10" class="tm-soft"/><text x="555" y="508" text-anchor="middle" class="tm-text" font-size="17" direction="rtl">اندازهٔ متغیر: رشتهٔ بدون تکرار</text><text x="555" y="539" text-anchor="middle" class="tm-text2" font-size="16" direction="rtl">اعتبار، زمان کوچککردن را تعیین میکند</text></svg>
```
مرزهای بسته و بازگرداندن اعتبار
| مرحله | \((left,right)\) | بازهٔ شامل دو سر | شمارشها | طول | بهترین طول |
| --- | --- | --- | --- | --- | --- |
| شرط پس از کوچککردن | \([left,right]\) | شمارشها دقیقاً متعلق به بازه | \(\forall c:\ counts[c]\le 1\) | \(right-left+1\) | ثبت فقط پس از اعتبار |
| بازهٔ خالی | \(left=0\)؛ هنوز ورودی نداریم | \(\varnothing\) | همه صفر | \(0\) | \(0\) |
| ورود a | \((0,0)\) | a | \(a:1\) | \(1\) | \(1\) |
| ورود b | \((0,1)\) | ab | \(a:1,\ b:1\) | \(2\) | \(2\) |
| ورود b؛ نامعتبر | \((0,2)\) | abb | \(a:1,\ b:2\) | \(3\)؛ ثبت نمیشود | \(2\) |
| حذف اول کافی نیست؛ while، نه if | \((1,2)\) | bb | \(a:0,\ b:2\) | \(2\)؛ ثبت نمیشود | \(2\) |
| حذف b قدیمی؛ معتبر | \((2,2)\) | b | \(a:0,\ b:1\) | \(1\) | \(2\) |
| ورود a؛ معتبر | \((2,3)\) | ba | \(a:1,\ b:1\) | \(2\) | \(2\) |
پیادهسازی sliding window با counts
**ورود از راست، حذف مکرر از چپ**
```python
def lengthoflongestsubstring(s):
counts = {}
left = best = 0
for right, ch in enumerate(s):
counts[ch] = counts.get(ch, 0) + 1
while counts[ch] > 1:
old = s[left]
counts[old] -= 1
if counts[old] == 0:
del counts[old]
left += 1
best = max(best, right - left + 1)
return best
```
**نکتهٔ جایگذاری:** بهروزرسانی `best` بیرون `while` و داخل حلقهٔ `for` است؛ یعنی فقط پس از معتبرشدن بازه.
**تمرین:** تابع را بدون نگاهکردن بنویس و روی `abba` قدمبهقدم اجرا کن؛ پاسخ باید \(2\) باشد.
دفاع از اعتبار، بهینگی و زمان
**اعتبار با invariant**
بازهٔ خالی معتبر است. ورود فقط برای همان کاراکتر تکرار میسازد؛ while تا رفع تکرار حذف میکند. شمارش بقیه فقط کم میشود؛ پس کل بازه دوباره معتبر است.
**دو حذف در abba**
پس از ورود b دوم:
\(\mathtt{abb}\rightarrow\mathtt{bb}\rightarrow\mathtt{b}\)
حذف a کافی نیست؛ حذف b قدیمی اعتبار را برمیگرداند.
**چرا بهترین جواب حفظ میشود؟**
شروعی که هر دو b را نگه دارد، اکنون و برای پایانهای بعدی نامعتبر است. فقط همین شروعها حذف میشوند؛ توقف در اولین بازهٔ معتبر یعنی بلندترین بازه برای هر right. سپس best بزرگترین طول را نگه میدارد.
**مجموع حرکتها، نه تعداد حلقهها**
right: دقیقاً \(n\) ورود؛ left: در کل حداکثر \(n\) خروج، بدون عقبرفتن.
\[n+n=2n\]
در abba: \(4\) ورود و \(2\) خروج.
**زمان و حافظه**
هر ورود و خروج با dict: زمان ثابتِ موردانتظار.
زمان کل موردانتظار: \(O(n)\).
حافظه: \(O(d)\)؛ \(d\) تعداد کاراکترهای متمایز ورودی است و counts کلید اضافی نگه نمیدارد.
تست مرزی و مرز اعتبار
| ورودی / حالت | ردگیری | نتیجه | نکته |
| --- | --- | --- | --- |
| رشتهٔ خالی | حلقه اجرا نمیشود | \(best=0\) | مقدار اولیه |
| `aaaa` | تعداد `a`: \(1\to2\to1\)؛ طول پس از حذف: \(1\) | \(best=1\) | هر بار یک حذف کافی است |
| `abcd` | طول: \(1\to2\to3\to4\) | \(best=4\) | بدون حذف |
| `abba` | `a` → `ab` → `b` → `ba` | \(best=2\) | حذف تا رفع کامل تکرار |
| `abba` با `if` | `abb` → `bb` → `bba`؛ فقط تعداد `a` بررسی میشود | \(best=3\)؛ نادرست | `while` تا رفع کامل تکرار؛ نه تعداد ثابت حذف |
| \([4,-2,1]\)، جمع \(\le3\) | حذف \(4\) → \([-2,1]\)، جمع \(-1\)؛ اما \(4-2+1=3\) | طول روش ساده: \(2\)؛ طول درست: \(3\) | شروع حذفشده بعداً مفید بود |
| شرط قاعدهٔ سادهٔ جمع | نامنفی: ورود از راست، جمع را کم نمیکند؛ حذف از چپ، جمع را زیاد نمیکند | مقدار منفی: بدون این تضمین | پیوستگی بهتنهایی کافی نیست |
Back to course