1.2 Sliding Window

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

"longest/shortest substring/subarray with X", contiguous, "subarray of size k", max/min sum — O(n²) nested loop-কে O(n) window-এ নামানো

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

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

Statement (Demo): string s ও t দেওয়া — s-এর সবচেয়ে ছোট substring বের করুন যাতে t-এর সব character (সংখ্যা সহ) থাকে। যদি না থাকে, "" return করুন। উদাহরণ: s="ADOBECODEBANC", t="ABC" → "BANC" | ⚡ len(s), len(t) ≤ 10⁵

Approach: t-এর প্রতিটা char-এর দরকারি count একটা map-এ রাখুন। ডান দিকে window বাড়ান; সব char পাওয়া গেলে (missing === 0) বাম দিক থেকে যত পারা যায় ছোট করুন আর best উত্তর আপডেট করুন। ছোট করতে গিয়ে কোনো দরকারি char হারালে আবার ডানে বাড়ানো শুরু।

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|)

প্রবলেম

Longest Substring Without Repeating Charactersplan · দিন ০০৯ LC 3
(hashing-ও লাগে — primary এখানেই)
Statement: string s দেওয়া — repeating character ছাড়া সবচেয়ে দীর্ঘ substring-এর দৈর্ঘ্য বের করুন।
উদাহরণ: "abcabcbb" → 3 ("abc") | ⚡ len ≤ 5×10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Longest Repeating Character ReplacementLC 424
Statement: uppercase string s ও integer k দেওয়া — সর্বোচ্চ kটা character পরিবর্তন করে সবচেয়ে দীর্ঘ same-letter substring-এর দৈর্ঘ্য বের করুন।
উদাহরণ: s="AABABBA", k=1 → 4 | ⚡ len ≤ 10⁵
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Fruit Into BasketsLC 904
(at most 2 distinct)
Statement: fruits array দেওয়া যেখানে fruits[i] = i-তম গাছের ফলের ধরন। দুটো basket নিয়ে যেকোনো একটানা গাছ থেকে সর্বোচ্চ কতটা ফল নেওয়া যায় বলুন (প্রতি basket-এ এক ধরনের ফল)।
উদাহরণ: [1,2,1,2,3] → 4 | ⚡ n ≤ 10⁵
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Minimum Size Subarray Sumplan · দিন ০১০ LC 209
Statement: positive integer target ও array nums দেওয়া — যোগফল ≥ target এমন সবচেয়ে ছোট contiguous subarray-এর দৈর্ঘ্য বের করুন। না থাকলে 0।
উদাহরণ: target=7, nums=[2,3,1,2,4,3] → 2 ([4,3]) | ⚡ n ≤ 10⁵
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Find All Anagrams in a StringLC 438
(fixed-size window + freq compare)
Statement: string s ও p দেওয়া — s-এ p-এর সব anagram-এর starting index-গুলো বের করুন।
উদাহরণ: s="cbaebabacd", p="abc" → [0,6] | ⚡ len(s),len(p) ≤ 3×10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন

আরও দেখুন

Sliding Window Maximum → দেখুন 4.4 (Stacks & Queues — monotonic deque)