Sliding Windowfixed window · variable window · expand / shrink · at most k

لما المسألة بتسأل عن جزء متصل (subarray أو substring)، مش لازم تحسب كل جزء from scratch. بتمسك window ليها بداية ونهاية وتزحلقها: عنصر يدخل من اليمين، وعنصر يطلع من الشمال. والنتيجة إن الـ O(n²) أو الـ O(n·k) بيبقوا O(n).

قبله: Two Pointers و Hash Map و Set بيمهّد لـ: Prefix Sum

هتطلع من الفصل ده وإنت عارف

  • تعرف من كلام المسألة إنها 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 اللي هنشيله.

تشبيه إنت قاعد جنب شباك قطر، والشباك بيبيّن 3 عمدان نور. لما القطر يتحرك مسافة عمود، مش بتبص على المنظر كله من الأول: عمود جديد بيظهر من قدّام، وعمود قديم بيختفي من ورا، والباقي زي ما هو. المجموع الجديد = القديم + اللي دخل ناقص اللي خرج.

ده الـ sliding window على نفس الـ array:

كل خطوة بقت عمليتين بس، مهما كان k كبير. يعني O(n) بدل O(n × k)، وعلى n = 100,000 ده حوالي 200 ألف عملية بدل 2.5 مليار.

طب إزاي تعرف من كلام المسألة إنها window أصلًا؟ ده الجزء الجاي.

إزاي تعرفه من المسألة

الـ keyword هنا متصل: subarray أو substring. لو عليه شرط، والمطلوب الأطول أو الأقصر أو الأكبر أو عدد الأجزاء، فكّر في sliding window على طول.

لما تشوف: subarraysubstringcontiguouslongest ... such that shortest / minimum lengthwindow of size kat most k without repeatingpositive integerspermutation / anagram inside a string
ومش هو غالبًا لو: subsequence (مش لازم متصل)sum equals k + negative numberscount subarrays with sum k (negatives)pick elements that are not adjacent

الـ subsequence بتنط على عناصر، فمش window، وغالبًا DP. والأرقام السالبة مع شرط على المجموع بتبوّظ الـ window خالص، وده هنشوفه في جزء "إمتى ما ينفعش".

النوعحجم الـ windowالـ left بيتحرك إمتىبتسجّل فينأشهر مسائل
ثابتة
fixed
k معروفكل خطوة، من أول ما الـ window تعدّي kكل خطوة بعد ما تكمل k643، 567، 438، 1456
متغيرة: الأطول
longest
بتكبر وتصغرطول ما هي invalidبعد الـ while3، 424، 1004، 904
متغيرة: الأقصر
shortest
بتكبر وتصغرطول ما هي validجوه الـ while209، 76
عدّ
count
بتكبر وتصغرطول ما هي invalidcount += right - left + 1 بعد الـ while1248، 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 واحد.

  1. بترجّع أكبر مجموع لـ k عناصر ورا بعض. الأرقام ممكن تبقى سالبة عادي هنا، والمسألة بتضمن k <= n.
  2. ليه best = -Infinity مش 0؟ لو كل الأرقام سالبة، الـ 0 عمره ما هيتكسب، وهترجّع رقم مش مجموع أي window.
  3. مفيش left متغير هنا، لأن بداية الـ window دايمًا right - k + 1. و < لأن آخر index هو n - 1.
  4. العنصر الجديد يدخل الأول، قبل أي check.
  5. لما right >= k الـ window بقت k + 1، فلازم يطلع واحد. اللي بيطلع right - k، لأن الـ window لازم تفضل [right - k + 1 .. right]. اتأكد: k = 3 و right = 3 يبقى يطلع index 0، ويفضل 1 و 2 و 3.
  6. أول window كاملة عند right = k - 1 (من 0 لـ k - 1). لو كتبت >= k هتفوّت أول window، ولو هي الإجابة يبقى Wrong Answer.
  7. كل 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:

  1. وسّع (expand): دخّل nums[right] وحدّث الـ state (مجموع، عدّاد، Set...).
  2. صغّر (shrink): طول ما الـ window invalid، طلّع nums[left] وحرّك left.
  3. سجّل (record): الـ window دلوقتي valid، فقارن طولها بالـ best.
تشبيه كوبري مشاة صغير بيستحمل وزن معيّن. الناس بتطلع من ناحية وتنزل من الناحية التانية بالترتيب. كل ما حد جديد يطلع والكوبري يتقل زيادة، أقدم واحد فوقه ينزل، ولو لسه تقيل ينزل اللي بعده. وكل لحظة الكوبري سليم فيها، بتعدّ اللي فوقه وتفتكر أكبر عدد.
  1. الأرقام موجبة، ودي مش تفصيلة: هي اللي مخلّية الـ template صح أصلًا. هنشوف ليه في جزء "إمتى ما ينفعش".
  2. الـ window فاضية، فـ sum = 0. و best = 0 مش -Infinity، لأن الطول عمره ما بيبقى سالب، ولو ولا عنصر نفع فالإجابة 0.
  3. right هو اللي بيسوق الـ loop وبيعدّي على كل عنصر مرة. و left عمره ما بيرجع لورا، ودي اللي هتخلّي الحل O(n).
  4. Expand: بندخّل العنصر الأول، وبعدين نسأل: الـ window لسه valid؟
  5. ليه while مش if؟ طلعة واحدة مش دايمًا كفاية: لما الـ 4 تدخل في الـ animation المجموع يبقى 10، ولازم يطلع الـ 2 والـ 1 الاتنين. والشرط مكتوب "طول ما هي invalid"، يعني sum > limit.
  6. الترتيب مهم: اطرح nums[left] الأول، وبعدين حرّك. لو عكست هتطرح العنصر اللي بعده، وهو لسه جوه الـ window، من غير أي error.
  7. Record بعد الـ while، لأن الـ window هنا valid أكيد. و + 1 لأننا بنعدّ عناصر (من 2 لـ 4 فيه 3)، مش بنقيس مسافة زي Container With Most Water. ولو الـ window فضيت (left = right + 1) الصيغة بتدّي 0، وده صح.
  8. لو ولا عنصر لوحده نفع، بترجع 0.
الـ invariant بعد سطر 8، الـ window [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")، الصورة بتتقلب:

longestshortest
الـ while بتلف طول ما الـ windowinvalid: بنصلّحهاvalid: بنحاول نصغّرها
بتسجّل فينبعد الـ whileجوه الـ while، قبل ما تطلّع العنصر
best بيبدأ بـ0Infinity، وترجّع 0 لو فضلت كده
بتقارن بـMath.maxMath.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 بيعدّ كل عنصر اتلمس كام مرة:

اسمها amortized analysis لفة واحدة من الـ while ممكن تبقى طويلة، بس مجموع كل اللفات محدود بـ 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 ليها نهاية واحدة، فبتتعدّ مرة واحدة بالظبط.

  1. بتعدّ الـ subarrays اللي فيها k أرقام فردية بالكتير. ده قلب حل LeetCode 1248.
  2. exactlyKOdd(nums, 0) بتنادي atMostKOdd(nums, -1)، و"-1 بالكتير" مستحيلة فالإجابة 0. من غير السطر ده، odd > -1 هيفضل true و left هيطلع برا الـ array.
  3. count هنا عدد بيتجمّع، مش أحسن طول.
  4. ليه !== 0 مش === 1؟ في JS، -3 % 2 بتطلع -1. فـ === 1 هتعتبر الـ -3 زوجي.
  5. الـ template بالظبط. ولو اللي خارج زوجي، بيطلع برضه عشان الـ window تفضل متصلة، بس العدّاد ما بيتغيّرش.
  6. قلب الحيلة: مش count++ ومش Math.max. ده عدد الـ windows الـ valid اللي بتخلص عند right.
  7. بالظبط 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 اللي بعدها كانت هتصلّح الموقف.

خلي بالك شرط على مجموع + أرقام ممكن تبقى سالبة (زي Subarray Sum Equals K) يبقى مش sliding window. الأداة الصح prefix sum مع hash map. اقرا الـ constraints دايمًا: لو لقيت -10⁴ <= nums[i]، اعرف إن الـ window غالبًا مش هي. أما مسائل الحروف (تكرار، عدد أنواع) فمفيهاش سالب، والـ monotonic فيها مضمون.

كده معاك الـ templates كلها. يلا نطبّقها على 5 مسائل، كل واحدة بتزوّد فكرة واحدة على اللي قبلها.

مثال محلول 1: Maximum Average Subarray I

نبدأ بالـ fixed window في أبسط صورة، بس بالطريقة التانية: نبني أول window لوحدها، وبعدين نزحلق.

Maximum Average Subarray I

easyLeetCode 643

عندك array أرقام (ممكن تبقى سالبة) ورقم k. هات أكبر متوسط لأي جزء متصل طوله k بالظبط.

Input: nums = [3, -1, 2, -4, 5, 6, -2, 1], k = 4 Output: 2.5 (window [5, 6, -2, 1]: sum 10, 10 / 4 = 2.5) Input: nums = [-3], k = 1 Output: -3

نفكّر فيها مع بعض

  1. افهم المطلوب: طول ثابت، يبقى fixed window. و k ثابت لكل الـ windows، فأكبر متوسط = أكبر مجموع ÷ k. نشتغل بالمجموع ونقسم مرة واحدة في الآخر.
  2. Brute force: كل window نجمعها من الأول، O(n × k).
  3. الخطة: ابني أول window واعتبرها الـ best، وبعدين زحلق: + اللي دخل، ناقص اللي خرج. O(1) لكل خطوة.
  4. Edge cases: كله سالب (الـ best ما يبدأش من 0)، k = n (window واحدة)، k = 1.
  1. أول window من 0 لـ k - 1. i < k مش i <= k، وإلا هتجمع k + 1 عنصر: مع k = 4 العناصر 0 و 1 و 2 و 3 بس.
  2. ليه best = sum مش 0؟ لو كله سالب، الـ 0 هيفضل الـ best وهترجّع 0، وده مش متوسط أي window. أول window إجابة حقيقية، فنبدأ بيها.
  3. نبدأ من k لأن العناصر من 0 لـ k - 1 دخلت خلاص. ولو k === n الـ loop مش هتلف، والإجابة أول window.
  4. سطر واحد للدخول والخروج. اللي خارج right - k، نفس حسبة الـ template.
  5. مفيش شرط right >= k - 1 هنا، لأن الـ window كاملة من الأول.
  6. القسمة مرة واحدة في الآخر: 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 = 25k = n: الـ loop التانية مش بتلف
[3, -1, 2, -4, 5, 6, -2, 1], k = 42.5أحسن window هي آخر واحدة، والإجابة كسر

التعقيد: O(n) وقت و O(1) memory.

هنا حجم الـ window معروف من الأول. طب لو حجمها نفسه هو المطلوب؟

مثال محلول 2: Longest Substring Without Repeating Characters

الجديد هنا إن الـ window متغيرة، والـ state مش مجموع: Set فيها الحروف اللي جوه الـ window.

Longest Substring Without Repeating Characters

mediumLeetCode 3

عندك string. هات طول أطول substring مفيهوش ولا حرف متكرر.

Input: s = "abcbade" → 5 ("cbade") Input: s = "abba" → 2 ("ab" or "ba") Input: s = "" → 0

نفكّر فيها مع بعض

  1. افهم المطلوب: متصل + أطول + شرط (مفيش تكرار)، يبقى variable window بتسجّل بعد الـ while.
  2. Brute force: كل substring وتتأكد إن مفيهوش تكرار: O(n³)، أو O(n²) لو وقفت أول ما تلاقي تكرار.
  3. الـ state: محتاجين نسأل بسرعة "الحرف ده جوه الـ window؟"، وده شغل Set: has في O(1).
  4. الـ window تبقى invalid إمتى؟ لما الحرف الجديد يكون جواها. فقبل ما ندخّله نسأل: لو موجود، نطلّع من الشمال لحد ما النسخة القديمة تخرج.
  5. Optimization: نفتكر آخر index لكل حرف في Map، و left يقفز لبعد النسخة القديمة مرة واحدة.
  6. Edge cases: string فاضي، "bbbb"، المسافة (حرف عادي)، و "abba" اللي بتوقّع نسخة الـ Map.

الطريقة الأولى: Set، والـ left بيمشي خطوة خطوة

  1. الـ Set فيها الحروف اللي جوه الـ window دلوقتي بالظبط. has و add و delete كلهم O(1) في المتوسط.
  2. الـ check قبل الـ add. بنسأل: "لو دخّلت s[right]، هيبقى فيه تكرار؟". الـ Set ما بتشيلش نسختين من نفس الحرف، فلازم القديمة تطلع الأول.
  3. بنطلّع s[left] مش s[right]. ممكن نطلّع حروف مش متكررة خالص عشان الـ window تفضل متصلة، لحد ما النسخة القديمة تطلع وتقف الـ while.
  4. دلوقتي s[right] مش موجود، فنضيفه ونسجّل الطول.
  5. لو الـ string فاضي، الـ loop مش هتلف، وبنرجّع 0.

الطريقة التانية: Map فيها آخر index، والـ left بيقفز

في الطريقة الأولى left بيمشي خطوة خطوة لحد ما يعدّي النسخة القديمة. لو حفظنا لكل حرف آخر index شفناه فيه، نقدر نحط left بعده مباشرة في خطوة واحدة.

  1. الـ Map فيها كل حرف شفناه من أول الـ string، مش بس اللي جوه الـ window، ومش بنمسح منها حاجة. ودي اللي بتعمل المشكلة في سطر 6.
  2. أهم سطر. مش كفاية الحرف يكون اتشاف قبل كده، لازم النسخة القديمة تكون جوه الـ window: last.get(ch) >= left. في "abba"، عند آخر a الـ left = 2 والـ a القديمة عند 0. من غير الشرط، left هيرجع لـ 1، والإجابة تطلع 3 بدل 2.
  3. نقفز لبعد النسخة القديمة، و + 1 عشان النسخة القديمة نفسها تخرج. بديل مشهور للسطور 6 لـ 8: left = Math.max(left, last.get(ch) + 1)، والـ max عمرها ما بترجّع left لورا.
  4. نحدّث الـ Map بعد الـ check، لأن الـ check محتاج المكان القديم.

نفس الـ string. راقب لما الـ a التانية تدخل: الـ Map فاكرة a عند 0، بس الـ 0 برا الـ window، فـ left ما بيتحركش:

SetMap (آخر index)
left بيتحرك إزايخطوة خطوةبيقفز مرة واحدة
الوقتO(n): كل حرف يدخل مرة ويخرج مرةO(n): لفة واحدة ومفيش while
الـ memoryO(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
في الانترفيو اسأل: الحروف إيه؟ lowercase بس؟ لو أيوه، تقدر تستخدم array of 26 بدل الـ Map، بـ s.charCodeAt(right) - 97. السؤال ده لوحده بيبيّن إنك بتفكّر في الـ input.

هنا بندوّر على الأطول. طب لو المطلوب الأقصر؟ الـ template هيتقلب.

مثال محلول 3: Minimum Size Subarray Sum

الجديد هنا إننا بندوّر على الأقصر، فالـ while بتلف وهي valid، والـ record بيتنقل جوه الـ while.

Minimum Size Subarray Sum

mediumLeetCode 209

عندك array أرقام موجبة ورقم target. هات طول أقصر subarray مجموعها ≥ target، ولو مفيش رجّع 0.

Input: target = 9, nums = [1, 4, 2, 6, 3, 1, 5] Output: 2 ([6, 3]) Input: target = 100, nums = [1, 2, 3] Output: 0

نفكّر فيها مع بعض

  1. افهم المطلوب: أقصر + متصل + شرط على مجموع + أرقام موجبة، يبقى sliding window. والموجبة بتضمن إن الـ shrink بيقلّل المجموع، والـ expand بيزوّده.
  2. Brute force: لكل بداية، امشي لحد ما المجموع يوصل. O(n²).
  3. الـ key insight: الـ window "الـ valid" هي اللي مجموعها ≥ target، وإحنا عايزين أصغرها. فطول ما هي valid: سجّل، وحاول تصغّر.
  4. Edge cases: مفيش إجابة (0)، عنصر واحد كفاية، الـ array كلها بالعافية تكفّي، وعنصر كبير في الآخر بيخلّي الـ while تلف كذا مرة.
  1. خلي بالك من ترتيب الـ parameters في LeetCode: target الأول.
  2. ليه best = Infinity؟ بندوّر على أصغر حاجة، فأي طول حقيقي لازم يكسب القيمة الابتدائية. مع best = 0، الـ Math.min هتفضل 0 دايمًا.
  3. ليه >= مش >؟ "على الأقل target" يعني target نفسه مقبول. بـ > هتفوّت [6, 3] اللي مجموعها 9 بالظبط، والإجابة تطلع 3.
  4. الـ record جوه، وقبل الطرح: في اللحظة دي الـ window valid أكيد. بعد سطري 7 و 8 ممكن تبقى invalid، ولو سجّلت بعد الـ while هتسجّل window مجموعها أقل من target.
  5. shrink بنفس الترتيب: اطرح وبعدين حرّك. والـ while تسأل تاني، ولو لسه valid هنسجّل طول أصغر بواحد.
  6. لو best فضلت Infinity يبقى ولا window وصلت، والمسألة عايزة 0. ما ترجّعش Infinity.
ليه ما فاتناش أي إجابة؟ لكل right، الـ while بتسجّل كل window valid بتخلص عنده من الأطول للأقصر. وأي window بتبدأ قبل left وبتخلص بعد كده، أطول من window valid سجّلناها قبل كده، فمستحيل تكسب.
Inputالمتوقعليه الحالة دي مهمة
100, [1, 2, 3]0best فضلت 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.

Longest Repeating Character Replacement

mediumLeetCode 424

عندك string حروفه capital إنجليزي بس، ورقم k. مسموحلك تغيّر k حرف بالكتير لأي حرف تاني. هات طول أطول substring ممكن تخلّيه كله حرف واحد.

Input: s = "AABCABBB", k = 2 Output: 6 ("BCABBB": change C and A to B) Input: s = "ABCD", k = 0 Output: 1

نفكّر فيها مع بعض

  1. افهم المطلوب: أطول + متصل + "k بالكتير"، يبقى variable window بتفكير at most k.
  2. إمتى window تبقى valid؟ الأوفر نخلّي كل الحروف زي الحرف الأكتر تكرار ونغيّر الباقي. فعدد التغييرات = طول الـ window - أكبر تكرار، والـ window valid لو ده ≤ k.
  3. الـ state: عدّاد 26 زي اللي في Arrays و Strings، ومتغير maxFreq.
  4. المشكلة: لما حرف يطلع، أكبر تكرار ممكن يقل، وحسابه من الأول بيلف على الـ 26. الـ trick: ما تقلّلش maxFreq خالص، وهنشرح ليه ده صح.
  5. Edge cases: k = 0 (أطول حتة حرف واحد)، k >= n (الإجابة n)، حرف واحد.
  1. عدّاد لكل حرف من A لـ Z. و .fill(0) مهمة: من غيرها الخانات undefined، و undefined + 1 بتطلع NaN.
  2. maxFreq معناها: أكبر تكرار شفناه في أي window لحد دلوقتي، مش في الـ window الحالية بالظبط. الفرق ده هو سر الحل.
  3. 'A' = 65، فـ - 65 بتحوّل A لـ 0 و Z لـ 25. لو الحروف small تبقى - 97.
  4. الحرف اللي دخل هو الوحيد اللي تكراره اتغيّر، فهو الوحيد اللي ممكن يكسر الـ max. عشان كده بنقارن بـ count[c] بس.
  5. (right - left + 1) - maxFreq = عدد الحروف اللي هنغيّرها. لو أكتر من k تبقى invalid. الـ while دي عمليًا بتلف مرة واحدة بالكتير، بس while مطابقة للـ template.
  6. shrink عادي، ومش بنلمس maxFreq، حتى لو الحرف اللي طلع هو صاحب أكبر تكرار.

ليه مش مشكلة إن maxFreq ما بتقلّش؟

بعد ما حرف يطلع، maxFreq ممكن تبقى أكبر من الحقيقي، فالكود يفتكر window "valid" وهي محتاجة أكتر من k تغيير. ليه ده ما بيضرّش؟

  1. الـ window عمرها ما بتصغر: كل خطوة right بيزوّد واحد، والـ while بتطلّع واحد بالكتير. فالطول يا يزيد، يا يفضل زي ما هو.
  2. عشان تكبر، لازم تكرار أكبر بجد: الشرط بيقول الطول ≤ maxFreq + k. فطول ما maxFreq ما زادتش، الـ window "الغلط" طولها = best اللي اتسجّل قبل كده من window valid بجد. مفيش إجابة كدابة.
  3. ولما يظهر تكرار أكبر بجد، maxFreq بتزيد في نفس الخطوة بقيمة حقيقية، والـ window تكبر، وده طول حقيقي.

الخلاصة: مش محتاجين نعرف أكبر تكرار دلوقتي، محتاجين نعرف هل نقدر نكسب best. راقب في الـ animation الخطوة اللي maxFreq فيها 3 والـ real max 2:

لو مش مرتاح للـ trick في الانترفيو احسب الـ max الحقيقي جوه الـ while بـ Math.max(...count). ده O(26n) = O(n)، صح ومقبول تمامًا. ابدأ بيه، وبعدين قول "وممكن ما نقلّلش maxFreq خالص، لأن..." واشرح النقط التلاتة.
Inputالمتوقعليه الحالة دي مهمة
"A", 01حرف واحد
"ABCD", 01k = 0: أطول حتة حرف واحد
"AAAA", 24الـ k الزيادة مش بتعدّي n
"AABCABBB", 26فيها خطوة maxFreq فيها قديمة، والإجابة لسه صح

التعقيد: O(n) وقت، و O(1) memory لأن الـ 26 ثابتة.

طب لو محتاج تقارن عدّاد الـ window كله بعدّاد string تانية؟

مثال محلول 5: Permutation in String

الجديد هنا إننا بنقارن عدّادين 26 كاملين في O(1) بعدّاد اسمه matches. والـ window ثابتة تاني، زي 643.

Permutation in String

mediumLeetCode 567

عندك s1 و s2 بحروف small. هل s2 جواها جزء متصل فيه نفس حروف s1 بالظبط، بأي ترتيب؟

Input: s1 = "abc", s2 = "dcbdacbe" Output: true ("acb" starts at index 4) Input: s1 = "abc", s2 = "ab" Output: false (s1 is longer)

نفكّر فيها مع بعض

  1. افهم المطلوب: permutation يعني نفس الحروف بنفس العدد. فالسؤال: فيه window في s2 طولها s1.length وعدد كل حرف فيها زي s1؟ الطول ثابت، يبقى fixed window.
  2. Brute force: لكل window رتّب حروفها وقارنها بـ s1 مترتبة: O(n × m log m).
  3. أحسن: need لـ s1 و have للـ window، ونقارن الـ 26 خانة كل خطوة. O(26n) = O(n)، ومقبول جدًا في انترفيو.
  4. الـ key insight: matches = عدد الحروف اللي have فيها = need. كل خطوة بتغيّر حرفين بس، فتحديثه O(1). ولما يبقى 26 نبقى لقيناها.
  5. Edge cases: s1 أطول من s2، s1 === s2، حروف مكررة زي "aab".
  1. early return: لو s1 أطول، مستحيل window في s2 تبقى قدها.
  2. need: كل حرف في s1 محتاج كام مرة. و - 97 لأن 'a' = 97.
  3. ليه matches بيبدأ بالحروف اللي need بتاعها 0؟ الـ window فاضية، فكل have = 0، والحروف اللي مش في s1 متطابقة من الأول. مع "abc" ده 23.
  4. الحرف الجديد دخل.
  5. أدق حتة: لو بعد الزيادة have === need، يبقى لسه واصل للتطابق: matches++. لو have === need + 1، يبقى كان متطابق وإحنا بوّظناه: matches--. غير كده التطابق ما اتغيّرش.
  6. نفس الـ fixed template: من أول right = k الـ window بقت k + 1، فيطلع s2[right - k].
  7. نفس المنطق بالعكس: have === need وصلنا، و have === need - 1 كان متطابق وبقى ناقص.
  8. ليه مش بنتأكد إن الـ window كاملة؟ لو فيها أقل من k حرف، أكيد فيه حرف have بتاعه ناقص، فـ matches مستحيل يوصل 26.

الصف letter بيقول كل عمود أنهي حرف، والأخضر في have يعني الحرف ده متطابق. الـ 21 حرف التانيين (f لـ z) متطابقين طول الوقت ومش مرسومين:

نفس الحل في مسائل تانية Find All Anagrams in a String (438) هي هي، بس بدل الـ return تحط right - k + 1 في list وتكمّل. وفكرة matches هي نفسها اللي بتحل Minimum Window Substring (76).
Inputالمتوقعليه الحالة دي مهمة
"abc", "ab"falses1 أطول: الـ 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 بس.

تمرين: فكّر قبل ما تفتح

Max Consecutive Ones III

mediumLeetCode 1004

array فيها 0 و 1 بس، ورقم k. مسموحلك تقلب k أصفار بالكتير لـ 1. هات أطول جزء متصل كله 1 بعد القلب.

[1, 0, 1, 1, 0, 0, 1, 1, 1, 0], k = 2 → 7 (indices 2..8)
تلميح 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 هحطه في إيه؟ هسجّل فين؟

وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.

الخلاصة

في جملة واحدة Sliding window هو اتنين pointers ماشيين لقدّام بس وبيحدّدوا جزء متصل: 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 حتى لو فيه سالب.