Sliding Windowfixed window · variable window · expand / shrink · at most k
لما المسألة بتسأل عن جزء متصل (subarray أو substring)، مش لازم تحسب كل جزء from scratch. بتمسك window ليها بداية ونهاية وتزحلقها: عنصر يدخل من اليمين، وعنصر يطلع من الشمال. والنتيجة إن الـ O(n²) أو الـ O(n·k) بيبقوا O(n).
هتطلع من الفصل ده وإنت عارف
- تعرف من كلام المسألة إنها sliding window، وإن الـ window fixed ولا variable.
- تكتب الـ template "وسّع، صغّر طول ما هي invalid، سجّل" من دماغك، وتعرف ليه
whileمشif، وليهright - left + 1. - تعرف تسجّل الإجابة فين: بعد الـ while للـ longest، وجوه الـ while للـ shortest.
- تفهم ليه الحل O(n) مع إن فيه loop جوه loop، وإمتى الـ pattern ده بيقع (الأرقام السالبة).
- تحل 643 و 3 و 209 و 424 و 567، وتشرحهم في انترفيو.
ليه Sliding Window؟
في الفصل اللي فات شفنا اتنين pointers ماشيين في نفس الاتجاه (read و write). دلوقتي هنخلّي الاتنين دول يحدّدوا window: كل العناصر اللي بينهم هي الجزء اللي بنفكّر فيه.
خد المسألة دي: عايز أكبر مجموع لـ k أرقام ورا بعض في array. الحل البديهي: لكل بداية ممكنة، اجمع الـ k أرقام.
خلي بالك من start + k <= nums.length. ليه <=؟ آخر window بتبدأ عند n - k، وعندها start + k = n بالظبط. لو كتبت < هتفوّت آخر window. مع n = 8 و k = 3: البدايات من 0 لـ 5، و 5 + 3 = 8 لازم تتقبل.
الحل ده بيعمل حوالي (n - k + 1) × k عملية جمع. مع n = 100,000 و k = 50,000 ده حوالي 2.5 مليار، يعني TLE أكيد. بص على الخانات الـ teal:
كل window بتشترك مع اللي قبلها في k - 1 رقم، والحل البديهي بيرجع يجمعهم تاني. ده الـ waste اللي هنشيله.
ده الـ sliding window على نفس الـ array:
كل خطوة بقت عمليتين بس، مهما كان k كبير. يعني O(n) بدل O(n × k)، وعلى n = 100,000 ده حوالي 200 ألف عملية بدل 2.5 مليار.
طب إزاي تعرف من كلام المسألة إنها window أصلًا؟ ده الجزء الجاي.
إزاي تعرفه من المسألة
الـ keyword هنا متصل: subarray أو substring. لو عليه شرط، والمطلوب الأطول أو الأقصر أو الأكبر أو عدد الأجزاء، فكّر في sliding window على طول.
الـ subsequence بتنط على عناصر، فمش window، وغالبًا DP. والأرقام السالبة مع شرط على المجموع بتبوّظ الـ window خالص، وده هنشوفه في جزء "إمتى ما ينفعش".
| النوع | حجم الـ window | الـ left بيتحرك إمتى | بتسجّل فين | أشهر مسائل |
|---|---|---|---|---|
| ثابتة fixed | k معروف | كل خطوة، من أول ما الـ window تعدّي k | كل خطوة بعد ما تكمل k | 643، 567، 438، 1456 |
| متغيرة: الأطول longest | بتكبر وتصغر | طول ما هي invalid | بعد الـ while | 3، 424، 1004، 904 |
| متغيرة: الأقصر shortest | بتكبر وتصغر | طول ما هي valid | جوه الـ while | 209، 76 |
| عدّ count | بتكبر وتصغر | طول ما هي invalid | count += right - left + 1 بعد الـ while | 1248، 992، 713 |
flowchart TD
A["Contiguous subarray or substring?"] -- no --> X["Not a window: subsequence means DP"]
A -- yes --> B{"Window size k given?"}
B -- yes --> F["Fixed window: add right, remove right - k"]
B -- no --> C{"Sum condition with negative numbers?"}
C -- yes --> P["Prefix sum + hash map"]
C -- no --> D{"Longest or shortest?"}
D -- longest --> L["Shrink while INVALID, record after the while"]
D -- shortest --> S["Shrink while VALID, record inside the while"]
اسأل نفسك الأسئلة دي بالترتيب ده.
يلا نبدأ بأسهل نوع: لما k معروف، والـ window حجمها ثابت.
النوع الأول: window ثابتة الحجم
لما k معروف، كل خطوة عنصر يدخل وعنصر يطلع. فيه طريقتين تكتبها بيهم: تبني أول window لوحدها وبعدين تزحلق (هتشوفها في مثال 643)، أو loop واحدة زي اللي تحت. ميزة الـ loop الواحدة إنها نفس شكل الـ variable window، فيفضل في دماغك template واحد.
- بترجّع أكبر مجموع لـ
kعناصر ورا بعض. الأرقام ممكن تبقى سالبة عادي هنا، والمسألة بتضمنk <= n. - ليه
best = -Infinityمش 0؟ لو كل الأرقام سالبة، الـ 0 عمره ما هيتكسب، وهترجّع رقم مش مجموع أي window. - مفيش
leftمتغير هنا، لأن بداية الـ window دايمًاright - k + 1. و<لأن آخر index هوn - 1. - العنصر الجديد يدخل الأول، قبل أي check.
- لما
right >= kالـ window بقتk + 1، فلازم يطلع واحد. اللي بيطلعright - k، لأن الـ window لازم تفضل[right - k + 1 .. right]. اتأكد:k = 3وright = 3يبقى يطلع index 0، ويفضل 1 و 2 و 3. - أول window كاملة عند
right = k - 1(من 0 لـk - 1). لو كتبت>= kهتفوّت أول window، ولو هي الإجابة يبقى Wrong Answer. - كل window كاملة اتقارنت، فـ
bestهو الإجابة.
right - k
ارسم 4 خانات بـ k = 3 و right = 3، واسأل: مين لازم يطلع عشان يفضل 3؟ هتلاقيه index 0، يعني 3 - 3. أي ±1 في window، اتأكد منه بمثال صغير كده قبل ما تكتبه.
طب لو المسألة ما ادتكش k، والـ window لازم تكبر وتصغر لوحدها على حسب شرط؟
النوع التاني: window متغيرة (الـ template الأساسي)
هنا المسألة بتقول "هات أطول جزء متصل بشرط كذا". مثالنا: array أرقام موجبة، وعايز طول أطول subarray مجموعها ≤ limit. الـ template تلات خطوات بتتكرر مع كل right:
- وسّع (expand): دخّل
nums[right]وحدّث الـ state (مجموع، عدّاد، Set...). - صغّر (shrink): طول ما الـ window invalid، طلّع
nums[left]وحرّكleft. - سجّل (record): الـ window دلوقتي valid، فقارن طولها بالـ best.
- الأرقام موجبة، ودي مش تفصيلة: هي اللي مخلّية الـ template صح أصلًا. هنشوف ليه في جزء "إمتى ما ينفعش".
- الـ window فاضية، فـ
sum = 0. وbest = 0مش-Infinity، لأن الطول عمره ما بيبقى سالب، ولو ولا عنصر نفع فالإجابة 0. rightهو اللي بيسوق الـ loop وبيعدّي على كل عنصر مرة. وleftعمره ما بيرجع لورا، ودي اللي هتخلّي الحل O(n).- Expand: بندخّل العنصر الأول، وبعدين نسأل: الـ window لسه valid؟
- ليه
whileمشif؟ طلعة واحدة مش دايمًا كفاية: لما الـ 4 تدخل في الـ animation المجموع يبقى 10، ولازم يطلع الـ 2 والـ 1 الاتنين. والشرط مكتوب "طول ما هي invalid"، يعنيsum > limit. - الترتيب مهم: اطرح
nums[left]الأول، وبعدين حرّك. لو عكست هتطرح العنصر اللي بعده، وهو لسه جوه الـ window، من غير أي error. - Record بعد الـ while، لأن الـ window هنا valid أكيد. و
+ 1لأننا بنعدّ عناصر (من 2 لـ 4 فيه 3)، مش بنقيس مسافة زي Container With Most Water. ولو الـ window فضيت (left = right + 1) الصيغة بتدّي 0، وده صح. - لو ولا عنصر لوحده نفع، بترجع 0.
[left..right] هي أطول window valid بتخلص عند right. كل مرة left اتحرك كان عشان window invalid، ومع أرقام موجبة أي window أطول منها invalid برضه. فلما right يوصل لنهاية الإجابة الحقيقية، إحنا ماسكينها.
[2, 1, 3, 4, 1, 1, 1] و limit = 7. الأزرق الـ window، والأحمر اللي كاسر الشرط أو خارج:
أطول ولا أقصر؟ تسجّل فين
اللي فوق للـ longest. لو المطلوب shortest window بتحقّق شرط (زي "مجموعها ≥ target")، الصورة بتتقلب:
| longest | shortest | |
|---|---|---|
| الـ while بتلف طول ما الـ window | invalid: بنصلّحها | valid: بنحاول نصغّرها |
| بتسجّل فين | بعد الـ while | جوه الـ while، قبل ما تطلّع العنصر |
best بيبدأ بـ | 0 | Infinity، وترجّع 0 لو فضلت كده |
| بتقارن بـ | Math.max | Math.min |
القاعدة اللي تفتكرها بدل الجدول: سجّل في اللحظة اللي الـ window فيها valid. هتشوفها عمليًا في مثال 209.
الـ window دلوقتي من left = 3 لـ right = 7. فيها كام عنصر؟
- 4
- 5
- 7
- 3
العناصر 3 و 4 و 5 و 6 و 7، يعني 5. الـ 7 - 3 = 4 دي المسافة، والعدد دايمًا المسافة + 1.
بس استنى: فيه while جوه for. ده مش O(n²)؟
ليه O(n) مع إن فيه while جوه for؟
لأن كل لفة في الـ while بتحرّك left one step لقدّام، و left عمره ما بيرجع. فعلى الحل كله، left بيمشي n خطوة بالكتير. الـ while مش بتلف n مرة لكل right، دي بتلف n مرة في المجموع.
بمعنى تاني: كل عنصر بيدخل مرة، وبيخرج مرة بالكتير، فكل الحركات ≤ 2n. الصف التاني في الـ animation بيعدّ كل عنصر اتلمس كام مرة:
n. زي مشوارك من أول الشارع لآخره: فيه خطوات بتمشي فيها كتير وخطوات ما بتمشيش، بس المسافة كلها طول الشارع وخلاص.
الـ brute force للـ variable window بيرجّع right لورا مع كل left جديد، فبيبقى O(n²). السر كله إن في الـ sliding window ولا pointer بيرجع.
طب لو الشرط "k بالكتير"، أو المطلوب تعدّ الـ windows مش تلاقي أطول واحدة؟
تفكير "at most k"
"k بالكتير" بتيجي كتير: اقلب k أصفار (1004)، غيّر k حروف (424)، نوعين فاكهة بالكتير (904). ودي كلها نفس الـ template بالظبط: الـ state عدّاد للحاجات "الوحشة"، والـ window invalid لما العدّاد يعدّي k، وبتسجّل بعد الـ while.
"بالظبط k" أصعب، فحوّلها لـ "at most"
لو المطلوب عدد الـ subarrays اللي فيها بالظبط k حاجة، الـ window المباشرة مش بتنفع، لأن "بالظبط" مش monotonic: window فيها 2 فردي، لو صغّرتها ممكن تبقى 1، ولو كبّرتها ممكن تبقى 3. الحيلة: exactly(k) = atMost(k) - atMost(k - 1).
وفي atMost بتعدّ إزاي؟ الـ key insight: لو [left..right] valid، كل subarray بتخلص عند right وبتبدأ من left أو بعده valid برضه، لأنها حتة منها. ودول right - left + 1. وكل subarray ليها نهاية واحدة، فبتتعدّ مرة واحدة بالظبط.
- بتعدّ الـ subarrays اللي فيها
kأرقام فردية بالكتير. ده قلب حل LeetCode 1248. exactlyKOdd(nums, 0)بتناديatMostKOdd(nums, -1)، و"-1 بالكتير" مستحيلة فالإجابة 0. من غير السطر ده،odd > -1هيفضل true وleftهيطلع برا الـ array.countهنا عدد بيتجمّع، مش أحسن طول.- ليه
!== 0مش=== 1؟ في JS،-3 % 2بتطلع-1. فـ=== 1هتعتبر الـ -3 زوجي. - الـ template بالظبط. ولو اللي خارج زوجي، بيطلع برضه عشان الـ window تفضل متصلة، بس العدّاد ما بيتغيّرش.
- قلب الحيلة: مش
count++ومشMath.max. ده عدد الـ windows الـ valid اللي بتخلص عندright. - بالظبط k = بالكتير k ناقص بالكتير k - 1. لفتين على الـ array، فبرضه O(n).
على [2, 1, 2, 1, 1, 2] و k = 2. الـ chip اللي اسمه new windows بيكتب الـ subarrays اللي اتعدّت في كل خطوة:
كل اللي فات كان على أرقام موجبة أو حروف. طب لو فيه أرقام سالبة؟
إمتى الـ sliding window ما ينفعش؟
الـ template كله قايم على إن الشرط monotonic: لو window invalid، أي window أكبر منها فيها نفس العناصر invalid برضه. ده اللي بيسمحلنا نرمي nums[left] للأبد من غير ما نندم.
مع الموجب ده صح: كل عنصر بتضيفه بيكبّر المجموع. بس مع السالب، عنصر جديد ممكن يصغّر المجموع، فـ window invalid ممكن ترجع valid لو كمّلت. نفس الـ template على [4, -5, 3] و limit = 2:
طلّع 2، والصح 3، لأن 4 - 5 + 3 = 2. رمينا الـ 4 في أول خطوة، والـ -5 اللي بعدها كانت هتصلّح الموقف.
-10⁴ <= nums[i]، اعرف إن الـ window غالبًا مش هي. أما مسائل الحروف (تكرار، عدد أنواع) فمفيهاش سالب، والـ monotonic فيها مضمون.
كده معاك الـ templates كلها. يلا نطبّقها على 5 مسائل، كل واحدة بتزوّد فكرة واحدة على اللي قبلها.
مثال محلول 1: Maximum Average Subarray I
نبدأ بالـ fixed window في أبسط صورة، بس بالطريقة التانية: نبني أول window لوحدها، وبعدين نزحلق.
عندك array أرقام (ممكن تبقى سالبة) ورقم k. هات أكبر متوسط لأي جزء متصل طوله k بالظبط.
نفكّر فيها مع بعض
- افهم المطلوب: طول ثابت، يبقى fixed window. و
kثابت لكل الـ windows، فأكبر متوسط = أكبر مجموع ÷k. نشتغل بالمجموع ونقسم مرة واحدة في الآخر. - Brute force: كل window نجمعها من الأول، O(n × k).
- الخطة: ابني أول window واعتبرها الـ best، وبعدين زحلق: + اللي دخل، ناقص اللي خرج. O(1) لكل خطوة.
- Edge cases: كله سالب (الـ best ما يبدأش من 0)،
k = n(window واحدة)،k = 1.
- أول window من 0 لـ
k - 1.i < kمشi <= k، وإلا هتجمعk + 1عنصر: معk = 4العناصر 0 و 1 و 2 و 3 بس. - ليه
best = sumمش 0؟ لو كله سالب، الـ 0 هيفضل الـ best وهترجّع 0، وده مش متوسط أي window. أول window إجابة حقيقية، فنبدأ بيها. - نبدأ من
kلأن العناصر من 0 لـk - 1دخلت خلاص. ولوk === nالـ loop مش هتلف، والإجابة أول window. - سطر واحد للدخول والخروج. اللي خارج
right - k، نفس حسبة الـ template. - مفيش شرط
right >= k - 1هنا، لأن الـ window كاملة من الأول. - القسمة مرة واحدة في الآخر:
kثابت، فترتيب المجاميع هو ترتيب المتوسطات. والـ/في JS بترجع الكسر (2.5)، مفيش integer division زي C++.
| Input | المتوسط | ليه الحالة دي مهمة |
|---|---|---|
| [-3], k = 1 | -3 | عنصر سالب لوحده: best = 0 كانت هترجّع 0 |
| [-1, -4, -2], k = 2 | -2.5 | كله سالب، والإجابة كسر سالب |
| [5, 5], k = 2 | 5 | k = n: الـ loop التانية مش بتلف |
| [3, -1, 2, -4, 5, 6, -2, 1], k = 4 | 2.5 | أحسن window هي آخر واحدة، والإجابة كسر |
التعقيد: O(n) وقت و O(1) memory.
هنا حجم الـ window معروف من الأول. طب لو حجمها نفسه هو المطلوب؟
مثال محلول 2: Longest Substring Without Repeating Characters
الجديد هنا إن الـ window متغيرة، والـ state مش مجموع: Set فيها الحروف اللي جوه الـ window.
عندك string. هات طول أطول substring مفيهوش ولا حرف متكرر.
نفكّر فيها مع بعض
- افهم المطلوب: متصل + أطول + شرط (مفيش تكرار)، يبقى variable window بتسجّل بعد الـ while.
- Brute force: كل substring وتتأكد إن مفيهوش تكرار: O(n³)، أو O(n²) لو وقفت أول ما تلاقي تكرار.
- الـ state: محتاجين نسأل بسرعة "الحرف ده جوه الـ window؟"، وده شغل Set:
hasفي O(1). - الـ window تبقى invalid إمتى؟ لما الحرف الجديد يكون جواها. فقبل ما ندخّله نسأل: لو موجود، نطلّع من الشمال لحد ما النسخة القديمة تخرج.
- Optimization: نفتكر آخر index لكل حرف في Map، و
leftيقفز لبعد النسخة القديمة مرة واحدة. - Edge cases: string فاضي،
"bbbb"، المسافة (حرف عادي)، و"abba"اللي بتوقّع نسخة الـ Map.
الطريقة الأولى: Set، والـ left بيمشي خطوة خطوة
- الـ Set فيها الحروف اللي جوه الـ window دلوقتي بالظبط.
hasوaddوdeleteكلهم O(1) في المتوسط. - الـ check قبل الـ add. بنسأل: "لو دخّلت
s[right]، هيبقى فيه تكرار؟". الـ Set ما بتشيلش نسختين من نفس الحرف، فلازم القديمة تطلع الأول. - بنطلّع
s[left]مشs[right]. ممكن نطلّع حروف مش متكررة خالص عشان الـ window تفضل متصلة، لحد ما النسخة القديمة تطلع وتقف الـ while. - دلوقتي
s[right]مش موجود، فنضيفه ونسجّل الطول. - لو الـ string فاضي، الـ loop مش هتلف، وبنرجّع 0.
الطريقة التانية: Map فيها آخر index، والـ left بيقفز
في الطريقة الأولى left بيمشي خطوة خطوة لحد ما يعدّي النسخة القديمة. لو حفظنا لكل حرف آخر index شفناه فيه، نقدر نحط left بعده مباشرة في خطوة واحدة.
- الـ Map فيها كل حرف شفناه من أول الـ string، مش بس اللي جوه الـ window، ومش بنمسح منها حاجة. ودي اللي بتعمل المشكلة في سطر 6.
- أهم سطر. مش كفاية الحرف يكون اتشاف قبل كده، لازم النسخة القديمة تكون جوه الـ window:
last.get(ch) >= left. في"abba"، عند آخرaالـleft = 2والـaالقديمة عند 0. من غير الشرط،leftهيرجع لـ 1، والإجابة تطلع 3 بدل 2. - نقفز لبعد النسخة القديمة، و
+ 1عشان النسخة القديمة نفسها تخرج. بديل مشهور للسطور 6 لـ 8:left = Math.max(left, last.get(ch) + 1)، والـmaxعمرها ما بترجّعleftلورا. - نحدّث الـ Map بعد الـ check، لأن الـ check محتاج المكان القديم.
نفس الـ string. راقب لما الـ a التانية تدخل: الـ Map فاكرة a عند 0، بس الـ 0 برا الـ window، فـ left ما بيتحركش:
| Set | Map (آخر index) | |
|---|---|---|
left بيتحرك إزاي | خطوة خطوة | بيقفز مرة واحدة |
| الوقت | O(n): كل حرف يدخل مرة ويخرج مرة | O(n): لفة واحدة ومفيش while |
| الـ memory | O(min(n, alphabet)) | O(min(n, alphabet)) |
| الفخ | قليل | لازم >= left أو Math.max |
الاتنين O(n)، والـ Map بتوفّر لفّات الـ while بس. في الانترفيو ابدأ بالـ Set لأنها أوضح، ولو اتسألت "تقدر تخلّي left يقفز؟"، قول الـ Map.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| "" | 0 | الـ loop مش بتلف |
| "bbbb" | 1 | كل حرف بيطلّع اللي قبله |
| " " | 1 | المسافة حرف عادي |
| "abba" | 2 | الـ Map من غير >= left بتطلّع 3 |
| "abcbade" | 5 | الـ Map من غير >= left بتطلّع 6 |
s.charCodeAt(right) - 97. السؤال ده لوحده بيبيّن إنك بتفكّر في الـ input.
هنا بندوّر على الأطول. طب لو المطلوب الأقصر؟ الـ template هيتقلب.
مثال محلول 3: Minimum Size Subarray Sum
الجديد هنا إننا بندوّر على الأقصر، فالـ while بتلف وهي valid، والـ record بيتنقل جوه الـ while.
عندك array أرقام موجبة ورقم target. هات طول أقصر subarray مجموعها ≥ target، ولو مفيش رجّع 0.
نفكّر فيها مع بعض
- افهم المطلوب: أقصر + متصل + شرط على مجموع + أرقام موجبة، يبقى sliding window. والموجبة بتضمن إن الـ shrink بيقلّل المجموع، والـ expand بيزوّده.
- Brute force: لكل بداية، امشي لحد ما المجموع يوصل. O(n²).
- الـ key insight: الـ window "الـ valid" هي اللي مجموعها ≥
target، وإحنا عايزين أصغرها. فطول ما هي valid: سجّل، وحاول تصغّر. - Edge cases: مفيش إجابة (0)، عنصر واحد كفاية، الـ array كلها بالعافية تكفّي، وعنصر كبير في الآخر بيخلّي الـ while تلف كذا مرة.
- خلي بالك من ترتيب الـ parameters في LeetCode:
targetالأول. - ليه
best = Infinity؟ بندوّر على أصغر حاجة، فأي طول حقيقي لازم يكسب القيمة الابتدائية. معbest = 0، الـMath.minهتفضل 0 دايمًا. - ليه
>=مش>؟ "على الأقل target" يعني target نفسه مقبول. بـ>هتفوّت[6, 3]اللي مجموعها 9 بالظبط، والإجابة تطلع 3. - الـ record جوه، وقبل الطرح: في اللحظة دي الـ window valid أكيد. بعد سطري 7 و 8 ممكن تبقى invalid، ولو سجّلت بعد الـ while هتسجّل window مجموعها أقل من target.
- shrink بنفس الترتيب: اطرح وبعدين حرّك. والـ while تسأل تاني، ولو لسه valid هنسجّل طول أصغر بواحد.
- لو
bestفضلتInfinityيبقى ولا window وصلت، والمسألة عايزة 0. ما ترجّعشInfinity.
right، الـ while بتسجّل كل window valid بتخلص عنده من الأطول للأقصر. وأي window بتبدأ قبل left وبتخلص بعد كده، أطول من window valid سجّلناها قبل كده، فمستحيل تكسب.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| 100, [1, 2, 3] | 0 | best فضلت Infinity |
| 5, [5] | 1 | المساوي مقبول: >= |
| 6, [1, 2, 3] | 3 | الـ array كلها بالعافية تكفّي |
| 7, [1, 1, 1, 7] | 1 | الـ while لازم تلف 4 مرات. بـ if الإجابة هتطلع 4 |
التعقيد: O(n) وقت و O(1) memory. والـ follow-up بتاع LeetCode (حل O(n log n)) بيتعمل بـ prefix sum و binary search، والحل اللي هنا أسرع منه أصلًا.
الـ state هنا كان مجموع. طب لو الشرط محتاج تعرف عدد كل حرف جوه الـ window؟
مثال محلول 4: Longest Repeating Character Replacement
الجديد هنا إن الـ state عدّاد لكل حرف، والـ validity محتاجة أكبر تكرار جوه الـ window. ومعاها أشهر trick في الـ sliding window.
عندك string حروفه capital إنجليزي بس، ورقم k. مسموحلك تغيّر k حرف بالكتير لأي حرف تاني. هات طول أطول substring ممكن تخلّيه كله حرف واحد.
نفكّر فيها مع بعض
- افهم المطلوب: أطول + متصل + "k بالكتير"، يبقى variable window بتفكير at most k.
- إمتى window تبقى valid؟ الأوفر نخلّي كل الحروف زي الحرف الأكتر تكرار ونغيّر الباقي. فعدد التغييرات =
طول الـ window - أكبر تكرار، والـ window valid لو ده ≤k. - الـ state: عدّاد 26 زي اللي في Arrays و Strings، ومتغير
maxFreq. - المشكلة: لما حرف يطلع، أكبر تكرار ممكن يقل، وحسابه من الأول بيلف على الـ 26. الـ trick: ما تقلّلش
maxFreqخالص، وهنشرح ليه ده صح. - Edge cases:
k = 0(أطول حتة حرف واحد)،k >= n(الإجابةn)، حرف واحد.
- عدّاد لكل حرف من A لـ Z. و
.fill(0)مهمة: من غيرها الخاناتundefined، وundefined + 1بتطلعNaN. maxFreqمعناها: أكبر تكرار شفناه في أي window لحد دلوقتي، مش في الـ window الحالية بالظبط. الفرق ده هو سر الحل.'A'= 65، فـ- 65بتحوّل A لـ 0 و Z لـ 25. لو الحروف small تبقى- 97.- الحرف اللي دخل هو الوحيد اللي تكراره اتغيّر، فهو الوحيد اللي ممكن يكسر الـ max. عشان كده بنقارن بـ
count[c]بس. (right - left + 1) - maxFreq= عدد الحروف اللي هنغيّرها. لو أكتر منkتبقى invalid. الـ while دي عمليًا بتلف مرة واحدة بالكتير، بسwhileمطابقة للـ template.- shrink عادي، ومش بنلمس
maxFreq، حتى لو الحرف اللي طلع هو صاحب أكبر تكرار.
ليه مش مشكلة إن maxFreq ما بتقلّش؟
بعد ما حرف يطلع، maxFreq ممكن تبقى أكبر من الحقيقي، فالكود يفتكر window "valid" وهي محتاجة أكتر من k تغيير. ليه ده ما بيضرّش؟
- الـ window عمرها ما بتصغر: كل خطوة
rightبيزوّد واحد، والـ while بتطلّع واحد بالكتير. فالطول يا يزيد، يا يفضل زي ما هو. - عشان تكبر، لازم تكرار أكبر بجد: الشرط بيقول الطول ≤
maxFreq + k. فطول ماmaxFreqما زادتش، الـ window "الغلط" طولها =bestاللي اتسجّل قبل كده من window valid بجد. مفيش إجابة كدابة. - ولما يظهر تكرار أكبر بجد،
maxFreqبتزيد في نفس الخطوة بقيمة حقيقية، والـ window تكبر، وده طول حقيقي.
الخلاصة: مش محتاجين نعرف أكبر تكرار دلوقتي، محتاجين نعرف هل نقدر نكسب best. راقب في الـ animation الخطوة اللي maxFreq فيها 3 والـ real max 2:
Math.max(...count). ده O(26n) = O(n)، صح ومقبول تمامًا. ابدأ بيه، وبعدين قول "وممكن ما نقلّلش maxFreq خالص، لأن..." واشرح النقط التلاتة.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| "A", 0 | 1 | حرف واحد |
| "ABCD", 0 | 1 | k = 0: أطول حتة حرف واحد |
| "AAAA", 2 | 4 | الـ k الزيادة مش بتعدّي n |
| "AABCABBB", 2 | 6 | فيها خطوة maxFreq فيها قديمة، والإجابة لسه صح |
التعقيد: O(n) وقت، و O(1) memory لأن الـ 26 ثابتة.
طب لو محتاج تقارن عدّاد الـ window كله بعدّاد string تانية؟
مثال محلول 5: Permutation in String
الجديد هنا إننا بنقارن عدّادين 26 كاملين في O(1) بعدّاد اسمه matches. والـ window ثابتة تاني، زي 643.
عندك s1 و s2 بحروف small. هل s2 جواها جزء متصل فيه نفس حروف s1 بالظبط، بأي ترتيب؟
نفكّر فيها مع بعض
- افهم المطلوب: permutation يعني نفس الحروف بنفس العدد. فالسؤال: فيه window في
s2طولهاs1.lengthوعدد كل حرف فيها زيs1؟ الطول ثابت، يبقى fixed window. - Brute force: لكل window رتّب حروفها وقارنها بـ
s1مترتبة: O(n × m log m). - أحسن:
needلـs1وhaveللـ window، ونقارن الـ 26 خانة كل خطوة. O(26n) = O(n)، ومقبول جدًا في انترفيو. - الـ key insight:
matches= عدد الحروف الليhaveفيها =need. كل خطوة بتغيّر حرفين بس، فتحديثه O(1). ولما يبقى 26 نبقى لقيناها. - Edge cases:
s1أطول منs2،s1 === s2، حروف مكررة زي"aab".
- early return: لو
s1أطول، مستحيل window فيs2تبقى قدها. need: كل حرف فيs1محتاج كام مرة. و- 97لأن'a'= 97.- ليه
matchesبيبدأ بالحروف الليneedبتاعها 0؟ الـ window فاضية، فكلhave= 0، والحروف اللي مش فيs1متطابقة من الأول. مع"abc"ده 23. - الحرف الجديد دخل.
- أدق حتة: لو بعد الزيادة
have === need، يبقى لسه واصل للتطابق:matches++. لوhave === need + 1، يبقى كان متطابق وإحنا بوّظناه:matches--. غير كده التطابق ما اتغيّرش. - نفس الـ fixed template: من أول
right = kالـ window بقتk + 1، فيطلعs2[right - k]. - نفس المنطق بالعكس:
have === needوصلنا، وhave === need - 1كان متطابق وبقى ناقص. - ليه مش بنتأكد إن الـ window كاملة؟ لو فيها أقل من
kحرف، أكيد فيه حرفhaveبتاعه ناقص، فـmatchesمستحيل يوصل 26.
الصف letter بيقول كل عمود أنهي حرف، والأخضر في have يعني الحرف ده متطابق. الـ 21 حرف التانيين (f لـ z) متطابقين طول الوقت ومش مرسومين:
right - k + 1 في list وتكمّل. وفكرة matches هي نفسها اللي بتحل Minimum Window Substring (76).
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| "abc", "ab" | false | s1 أطول: الـ early return |
| "ab", "ab" | true | الـ window الوحيدة هي s2 كلها |
| "aab", "baa" | true | حروف مكررة: need[a] = 2 |
| "ab", "eidboaoo" | false | الحروف موجودة بس مش جنب بعض |
التعقيد: O(m + n) وقت، و O(1) memory (الـ 26 ثابتة).
دي الحلول الصح. يلا نشوف الغلطات اللي بتوقّع الناس في نفس الكود ده.
غلطات مشهورة
كل غلطة هنا الكود بيعدّي بيها على أمثلة كتير، وبعدين يقع في test واحد.
1. if بدل while
لما الـ 7 دخلت، الـ window كانت ممكن تتصغّر 3 مرات لحد [7]، والـ if صغّرتها مرة واحدة. استخدم while دايمًا، حتى لو بتلف مرة واحدة زي 424.
2. right - left بدل right - left + 1
الـ window فيها right - left + 1 عنصر. من غير + 1 ده عرض بين حيطتين، وينفع في Container With Most Water بس.
3. في الأقصر: سجّلت بعد الـ while
الـ while ما بتقفش غير لما الشرط يتكسر، فبعدها الـ window invalid أكيد، والكود ده بيسجّل حتى لو عمر الـ window ما وصلت لـ target. سجّل في اللحظة اللي الـ window فيها valid.
4. حرّكت left قبل ما تطرح
اللي خارج هو اللي واقف عند left دلوقتي. اطرحه الأول وبعدين اتحرك، ونفس الكلام في الـ Set: delete(s[left]) وبعدين left++.
5. الـ Map من غير >= left
الـ Map فيها نسخ قديمة برا الـ window، والقفز عليها بيرجّع left لورا. أي سطر بيحرّك left، اسأل: ممكن يرجّعه؟
6. sliding window على أرقام سالبة
الـ template على [4, -5, 3] و limit = 2 طلّع 2، والصح 3، لأن الـ monotonic بيقع مع السالب. الحل prefix sum. ومن نفس العيلة: في 643 لو بدأت best = 0، [-3, -1, -2] و k = 2 هتطلّع 0 بدل -1.5.
دلوقتي جرّب نفسك: كام سؤال سريع، وتمرين تفكّر فيه قبل ما تفتح الحل.
اختبر نفسك
"أقصر subarray مجموعها ≥ target، والأرقام موجبة". تسجّل الإجابة فين؟
- بعد الـ while
- جوه الـ while، قبل ما تطلّع العنصر
- قبل الـ while، بعد ما العنصر يدخل على طول
- مرة واحدة بعد الـ for
في الأقصر الـ while بتلف وهي valid، وكل لفة فيها window أقصر من اللي قبلها. بعد الـ while هي invalid أكيد، وقبلها إنت بتسجّل الأطول بس.
ليه الـ variable window بتاخد O(n) مع إن فيه while جوه for؟
- لأن الـ while بتلف مرة واحدة بس في كل خطوة
- لأن
leftعمره ما بيرجع، فمجموع لفّات الـ while على الحل كله ≤ n - لأن الـ JS بتعمل optimize للـ loops
- غلط، هي O(n²) في الـ worst case
لفة واحدة ممكن تبقى طويلة (في [1, 1, 1, 7] لفّت 4 مرات ورا بعض)، بس كل عنصر بيطلع مرة واحدة بالكتير، فالمجموع ≤ n، ومعاه n دخول.
"عدد الـ subarrays اللي مجموعها k بالظبط"، والأرقام فيها سالب. تستخدم إيه؟
- Sliding window: صغّر طول ما المجموع أكبر من k
- Two pointers من الطرفين بعد sort
- Prefix sum مع hash map
- Fixed window بحجم k
مع السالب الشرط مش monotonic، فالـ window هترمي عناصر كان ليها إجابة. والـ sort بيبوّظ "متصل". الحل في الفصل الجاي.
في 424، ليه مقبول إن maxFreq ما تقلّش لما حرف يطلع؟
- لأن الحرف الأكتر تكرار عمره ما بيطلع من الشمال
- لأن الإجابة ما بتكبرش غير بتكرار أكبر من أي تكرار شفناه، والقيمة القديمة بتخلّي الـ window تتزحلق بنفس طولها بس
- لأن
kبيعوّض الفرق - مش مقبول، ده bug بس الـ tests ما مسكتهوش
الـ window ما بتصغرش، وعشان تكبر عن best لازم maxFreq تزيد بقيمة حقيقية. فأقصى ضرر للقيمة القديمة window "غلط" بنفس طول best اللي اتسجّل من window valid.
Fixed window بـ k = 4، و right = 9 لسه داخل. مين اللي يطلع؟
- index 4
- index 5
- index 6
- index 8
right - k = 9 - 4 = 5، والـ window تفضل [6..9]: أربعة عناصر. لو طلّعت 6 هيفضل 3 بس.
تمرين: فكّر قبل ما تفتح
array فيها 0 و 1 بس، ورقم k. مسموحلك تقلب k أصفار بالكتير لـ 1. هات أطول جزء متصل كله 1 بعد القلب.
تلميح 1
ما تفكّرش "أقلب أنهي صفر". اقلب السؤال: أطول window فيها k أصفار بالكتير. أي window زي دي تقدر تقلب كل أصفارها.
تلميح 2
الـ state عدّاد أصفار. invalid لما zeros > k، فصغّر لحد ما يرجع ≤ k. وهي "أطول"، فسجّل بعد الـ while.
الحل
نفس الـ template سطر بسطر، والـ state بس اتغيّر من مجموع لعدّاد أصفار. مع [0, 0, 0] و k = 0 بيرجّع 0. O(n) وقت و O(1) memory.
لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.
اتمرن على LeetCode بالترتيب
كل مسألة بتضيف فكرة واحدة جديدة، والتقدّم بيتحفظ. قبل أي حل اسأل نفسك: الـ window fixed ولا variable؟ الـ state هحطه في إيه؟ هسجّل فين؟
- Maximum Average Subarray Iالمثال المحلول 1. أبسط fixed window: سخّن بيه إيدك.
- Maximum Number of Vowels in a Substringfixed window على string، والـ state عدّاد بدل مجموع.
- Contains Duplicate IIfixed window حالتها Set: اللي برا الـ window يتمسح منها.
- Longest Substring Without Repeating Charactersالمثال المحلول 2. اكتب الطريقتين: Set و Map.
- Minimum Size Subarray Sumأول "أقصر": الـ record جوه الـ while.
- Max Consecutive Ones IIIالتمرين اللي فوق: at most k بأوضح شكل.
- Longest Repeating Character Replacementالمثال المحلول 4. اشرح trick الـ maxFreq لنفسك بصوت عالي.
- Permutation in Stringالمثال المحلول 5: عدّادين 26 وعدّاد matches.
- Find All Anagrams in a Stringنفس 567، بس بتجمع كل البدايات بدل ما ترجع أول ما تلاقي.
- Fruit Into Basketsنوعين بالكتير: الـ state Map فيها عدد كل نوع، وتمسح النوع لما عدّاده يبقى 0.
- Count Number of Nice Subarraysأول عدّ: exactly(k) = atMost(k) - atMost(k - 1).
- Subarrays with K Different Integersنفس حيلة العدّ، والـ state Map زي 904.
- Minimum Window Substringأقصر + عدّادات + matches. لو حليتها يبقى الـ pattern في جيبك.
- Sliding Window Maximumاختياري: fixed window محتاجة deque عشان الـ max. ارجعلها بعد Queue و Deque.
وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.
الخلاصة
right بيدخّل، و left بيطلّع لما الشرط يتكسر. وده بيشتغل بس لو الشرط monotonic: لو window invalid، أي window أكبر منها invalid برضه.
remove(nums[left++]) بتشيل اللي عند left القديم وبعدين تحرّكه، يعني نفس الترتيب الصح.
| السؤال | الإجابة |
|---|---|
while ولا if؟ | while دايمًا. |
| طول الـ window؟ | right - left + 1: عدد عناصر، مش مسافة. |
| أسجّل فين؟ | في اللحظة اللي الـ window فيها valid: بعد الـ while للأطول، جوه الـ while للأقصر. |
best يبدأ بإيه؟ | الأطول 0. الأقصر Infinity وترجّع 0 لو فضلت. أكبر مجموع -Infinity أو أول window. |
| مين بيطلع في الـ fixed؟ | nums[right - k]، والـ record من right >= k - 1. |
| الـ state أحطه في إيه؟ | مجموع، عدّاد، Set (موجود ولا لأ)، Map أو array of 26 (عدد كل حاجة). |
| "بالظبط k"؟ | atMost(k) - atMost(k - 1). |
| أرقام سالبة مع شرط على المجموع؟ | مش sliding window: prefix sum + hash map. |
| Complexity؟ | O(n) وقت. والـ memory O(1) لمجموع أو 26، و O(alphabet) لـ Set أو Map. |
الفصل الجاي: Prefix Sum بيحل بالظبط المكان اللي الـ window وقعت فيه. بدل ما تفترض إن المجموع بيكبر مع كل عنصر، بتحسب مرة واحدة مجموع كل بداية، وتجيب مجموع أي جزء بطرح رقمين. ومع hash map بتعدّ الـ subarrays اللي مجموعها k حتى لو فيه سالب.