1.2 Sliding Window

চিনবেন কীভাবে

"longest/shortest substring/subarray with X", contiguous, "subarray of size k", max/min sum — turns an O(n²) nested loop into an O(n) window

Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Minimum Window Substring — LC 76 (Hard — Google/Meta/Apple High)

Statement (Demo): Given strings s and t, return the shortest substring of s that contains every character of t (with multiplicity). Return "" if there is none. Example: s="ADOBECODEBANC", t="ABC" → "BANC" | ⚡ len(s), len(t) ≤ 10⁵

Approach: Keep the required count of each character of t in a map. Grow the window to the right; once every character is covered (missing === 0), shrink from the left as far as possible and record the best answer. When shrinking drops a required character, go back to growing.

function minWindow(s, t) {
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  let missing = t.length,
    l = 0,
    best = [0, Infinity];
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    if (need.has(c)) {
      if (need.get(c) > 0) missing--;
      need.set(c, need.get(c) - 1);
    }
    while (missing === 0) {
      // valid window → shrink
      if (r - l < best[1] - best[0]) best = [l, r];
      const d = s[l];
      if (need.has(d)) {
        need.set(d, need.get(d) + 1);
        if (need.get(d) > 0) missing++;
      }
      l++;
    }
  }
  return best[1] === Infinity ? "" : s.slice(best[0], best[1] + 1);
}

Complexity: Time O(|s| + |t|), Space O(|t|)

Demo · Minimum Window Substringplan · দিন ০৩৮ LC 76

নোট · ফাঁকা

My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে

প্রবলেম

Longest Substring Without Repeating Charactersplan · দিন ০০৩🔥 Must-doLC 3
(needs hashing too — primary entry is here)
Statement: Given a string s, return the length of the longest substring with no repeated character.
Example: "abcabcbb" → 3 ("abc") | ⚡ len ≤ 5×10⁴
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Longest Repeating Character Replacementplan · দিন ০১৫🔥 Must-doLC 424
Statement: Given an uppercase string s and an integer k, change at most k characters and return the length of the longest substring made of a single letter.
Example: s="AABABBA", k=1 → 4 | ⚡ len ≤ 10⁵
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Fruit Into BasketsLC 904
(at most 2 distinct)
Statement: fruits[i] is the fruit type of tree i. With two baskets, each holding one type, return the most fruit you can pick from a contiguous run of trees.
Example: [1,2,1,2,3] → 4 | ⚡ n ≤ 10⁵
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Minimum Size Subarray Sumplan · দিন ০২২🔥 Must-doLC 209
Statement: Given a positive integer target and an array nums, return the length of the shortest contiguous subarray whose sum is ≥ target, or 0 if none exists.
Example: target=7, nums=[2,3,1,2,4,3] → 2 ([4,3]) | ⚡ n ≤ 10⁵
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Find All Anagrams in a Stringplan · দিন ০৩৯ LC 438
(fixed-size window + frequency compare)
Statement: Given strings s and p, return every starting index in s where an anagram of p begins.
Example: s="cbaebabacd", p="abc" → [0,6] | ⚡ len(s),len(p) ≤ 3×10⁴
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে

আরও দেখুন

Sliding Window Maximum → see 4.4 (Stacks & Queues — monotonic deque)