020 — Minimum Window Substring

Problem link ও উৎস

• Original source: Classic shrinkable sliding-window exercise
• Platform: LeetCode — https://leetcode.com/problems/minimum-window-substring/
• Topic: string / sliding window
• Difficulty: Hard
• Pattern: sliding window (shrinkable) + frequency counting
• Basic idea inherited from: Longest-unique window (problem 10) + character counts — expand করে valid বানাও, তারপর shrink করে minimal

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

দুটো string s আর t দেওয়া। s-এর এমন সবচেয়ে ছোট substring (window) খুঁজে বের করো যেটার ভেতরে t-এর প্রতিটা character অন্তত যতবার t-তে আছে, ততবার আছে (multiplicity সহ)। এমন window না থাকলে খালি string ফেরত দাও।

উদাহরণ

s = "ADOBECODEBANC", t = "ABC"
A, B, C তিনটাই ধরে এমন সবচেয়ে ছোট window: "BANC"

Input ও output

উদাহরণ

Input : s = "ADOBECODEBANC", t = "ABC" -> "BANC"
Input : s = "a", t = "a"               -> "a"

Edge case 1 (যথেষ্ট char নেই): s = "a", t = "aa" -> ""
Edge case 2 (s খালি/অমিল):     s = "",  t = "a"  -> ""

চেনা উদাহরণে বোঝা

ভাবো একটা shopping list (t) আছে — 1টা আপেল, 1টা কলা, 1টা চেরি। তুমি একটা লম্বা তাকের (s) সামনে দিয়ে হাঁটছ, ডান হাতে জিনিস তুলছ যতক্ষণ না list-এর সব আইটেম জোগাড় হয়। জোগাড় হওয়ার সাথে সাথে বাঁ দিক থেকে অপ্রয়োজনীয় জিনিস ফেলে দিতে থাকো — কোনো দরকারি আইটেম কমে গেলে থামো। সবচেয়ে আঁটোসাঁটো ঝুড়িটাই উত্তর।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত হলো sliding window (problem 10, Longest Substring Without Repeating)। সেখানে ছিল "longest valid window"; এখানে চাই "shortest valid window" — তাই দিক উল্টো: ডান প্রান্ত right দিয়ে window বড় করে valid বানাই, valid হওয়ার সাথে সাথে বাঁ প্রান্ত left দিয়ে যতটা সম্ভব ছোট করি। সাথে problem 3-এর character count লাগে — কোন অক্ষর কতবার দরকার তা মেলাতে। sliding-window-এর math: ../../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/।

ভেতরের যুক্তি

লুকানো logic দুটো invariant: (১) right শুধু সামনে যায়, left-ও শুধু সামনে যায় — তাই দুটো মিলে মোট 2n ধাপ, O(n)। (২) একটা গণনা formed রাখি = t-এর কয়টা আলাদা অক্ষরের চাহিদা এখন পুরোপুরি মিটেছে। formed == required (t-এর আলাদা অক্ষর সংখ্যা) হলেই window valid — তখন left-কে এগিয়ে ছোট করার চেষ্টা করি, যতক্ষণ valid থাকে।

কী দিয়ে তথ্য রাখব

দুটো hash map (dict): need (t-এর প্রতিটা অক্ষর কতবার লাগবে) আর window (চলতি window-এ প্রতিটা অক্ষর কতবার আছে)। সাথে কয়েকটা integer: left, formed, required, আর সেরা window-এর best_len/best_left।

এটি কেন উপযুক্ত

প্রশ্নটা গণনা-নির্ভর: "এই অক্ষর কি চাহিদার সমান হলো?" — dict-এ count বাড়ানো/কমানো ও তুলনা সবই average O(1)। formed counter রাখায় প্রতিবার পুরো need map স্ক্যান করে "সব মিটেছে কিনা" দেখার দরকার পড়ে না — শুধু যে অক্ষরটা এইমাত্র ঠিক চাহিদায় পৌঁছাল, তার জন্য formed এক বাড়াই/কমাই।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: s-এর প্রতিটা শুরু-index থেকে প্রতিটা শেষ-index পর্যন্ত সব substring বানাও, প্রতিটার জন্য check করো সেটা t-এর সব char ধরে কিনা, valid হলে সবচেয়ে ছোটটা রাখো।

উদাহরণ

best = None
for i in range(n):
    for j in range(i, n):
        if window s[i..j] contains all of t (count check):
            best = shorter(best, s[i..j])

কোথায় বেশি কাজ হচ্ছে

সব substring O(n^2)টা, প্রতিটার জন্য আবার count-check O(n) — মোট O(n^3) (বা সাবধানে O(n^2))। বারবার overlapping window নতুন করে গোনা হচ্ছে। sliding window সেই কাজ পুনর্ব্যবহার করে: window এক ঘর বাড়লে শুধু একটা count update হয়, পুরোটা আবার গোনা লাগে না — মোট O(n)।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: একটা valid window পেলে, আরও বড় করে নতুন valid খোঁজার দরকার নেই — বরং বাঁ দিক থেকে ছেঁটে minimal করো, তারপর ডান প্রান্ত আবার বাড়িয়ে পরের valid খোঁজো। formed counter থাকায় "valid কিনা" O(1)-এ জানা যায়, পুরো map স্ক্যান লাগে না।

আরও কম কাজে সমাধান

need = Counter(t), required = len(need) (আলাদা অক্ষরের সংখ্যা)। right দিয়ে window বাড়াও; কোনো অক্ষরের window-count যখন ঠিক তার need-count ছুঁলো, formed += 1। যখন formed == required (valid), ভেতরের while-এ left এগিয়ে window ছোট করো — সবচেয়ে ছোট দৈর্ঘ্য update করতে করতে — যতক্ষণ না কোনো দরকারি অক্ষর চাহিদার নিচে নামে (তখন formed -= 1, valid ভাঙে)। right শেষ পর্যন্ত। মোট O(|s| + |t|)।

ভাবনার পরিবর্তন

মোচড়: "সব substring বানিয়ে check করব" ভোলো। ভাবো "ডান হাত দিয়ে যথেষ্ট জোগাড় করি (expand-to-valid), তারপর বাঁ হাত দিয়ে যতটা পারি ছেঁটে ফেলি (shrink-to-minimal)।" দুই প্রান্তই শুধু সামনে যায়, তাই overlapping কাজ একবারও দুবার হয় না।

ছবিতে বোঝা

s="ADOBECODEBANC", t="ABC"। প্রতিটি R এবং valid হলে সব shrink নিচে আছে। Count বলতে শুধু A/B/C-এর চাহিদা মিটেছে কি না দেখি; অন্য অক্ষরও window-তে থাকে।

R / অক্ষর	L (নতুন অক্ষর নেওয়ার আগে)	কী ঘটল	shrink শেষে L	best
0 / A	0	A আছে; B,C নেই	0	নেই
1 / D	0	B,C নেই	0	নেই
2 / O	0	B,C নেই	0	নেই
3 / B	0	C নেই	0	নেই
4 / E	0	C নেই	0	নেই
5 / C	0	ADOBEC valid; A বাদ দিলে invalid	1	ADOBEC (6)
6 / O	1	A নেই	1	ADOBEC (6)
7 / D	1	A নেই	1	ADOBEC (6)
8 / E	1	A নেই	1	ADOBEC (6)
9 / B	1	A নেই; B এখন দুইটি	1	ADOBEC (6)
10 / A	1	valid; D,O,B,E বাদ দিয়েও valid; C বাদ দিলে invalid	6	ADOBEC (6)
11 / N	6	C নেই	6	ADOBEC (6)
12 / C	6	O,D,E বাদ: BANC valid; B বাদ দিলে invalid	10	BANC (4)

R=10-এ valid candidate-গুলো DOBECODEBA, OBECODEBA, BECODEBA, ECODEBA, CODEBA; শেষটির দৈর্ঘ্যও 6। R=12-এ ODEBANC → DEBANC → EBANC → BANC; তাই 4 হলো নতুন সেরা।

ছোট input-এ ধাপে ধাপে

Input s = "a", t = "a":

1. need = {a:1}, required = 1, formed = 0, left = 0, best_len = ∞।
2. right=0 'a': window={a:1}; a need-এ আর window[a]==need[a] → formed=1।
3. formed == required (1==1) → valid। দৈর্ঘ্য 0-0+1=1 < ∞ → best_len=1, best_left=0। shrink: left_ch='a', window[a]=0 < need[a] → formed=0, left=1। while শেষ।
4. right শেষ। best_len=1 → s[0:1] = "a"।

কোড ও ব্যাখ্যা

Python

Python

from collections import Counter

def min_window(s, t):
    if not s or not t:
        return ""
    need = Counter(t)
    required = len(need)               # t-এর আলাদা অক্ষরের সংখ্যা
    window = {}
    formed = 0                         # কয়টা আলাদা অক্ষরের চাহিদা পুরো হয়েছে
    left = 0
    best_len = float("inf")
    best_left = 0
    for right, ch in enumerate(s):
        window[ch] = window.get(ch, 0) + 1
        if ch in need and window[ch] == need[ch]:
            formed += 1                # এই অক্ষর ঠিক চাহিদায় পৌঁছাল
        while formed == required:      # window valid -> ছোট করার চেষ্টা
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_left = left
            left_ch = s[left]
            window[left_ch] -= 1
            if left_ch in need and window[left_ch] < need[left_ch]:
                formed -= 1            # দরকারি অক্ষর কমে গেল -> valid ভাঙল
            left += 1
    return "" if best_len == float("inf") else s[best_left:best_left + best_len]

# ---- tests ----
assert min_window("ADOBECODEBANC", "ABC") == "BANC"
assert min_window("a", "a") == "a"
assert min_window("a", "aa") == ""        # যথেষ্ট 'a' নেই
assert min_window("", "a") == ""          # s খালি
print("সব test pass!")

কোডের প্রতিটি অংশ

• need = Counter(t) — প্রতিটা অক্ষর কতবার লাগবে।
• required = len(need) — কয়টা আলাদা অক্ষরের চাহিদা মেটাতে হবে।
• window[ch] = window.get(ch,0)+1 — ডান প্রান্তের অক্ষর window-এ যোগ।
• if ch in need and window[ch] == need[ch]: formed += 1 — ঠিক চাহিদার সমান হলেই (বেশি হলে নয়) এক ধাপ এগোলাম।
• while formed == required: — window এখন সব চাহিদা মেটায়; এর ভেতরে যতটা পারি ছোট করি।
• if right-left+1 < best_len: — এই valid window আগের সেরার চেয়ে ছোট হলে রাখি।
• window[left_ch] -= 1; if ... < need: formed -= 1 — বাঁ প্রান্ত ছাঁটি; দরকারি অক্ষর চাহিদার নিচে নামলে valid ভাঙে, loop থামে।
• শেষ line — কোনো valid না পেলে "", নইলে best স্লাইস।

Output মিলিয়ে দেখা

"ADOBECODEBANC"/"ABC" → expand-shrink করতে করতে সবচেয়ে ছোট valid "BANC" (4) → assert pass। "a"/"a" → "a"; "a"/"aa" → দুটো a দরকার, একটাই আছে, কখনো valid হয় না → ""; ""/"a" → guard-এ ""। শেষে print: সব test pass!।

JavaScript ও test cases

দুই Map (need/window) + formed counter — expand-to-valid, তারপর shrink-to-minimal।

JavaScript

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// smallest substring of s containing all chars of t (with multiplicity)
function minWindow(s, t) {
  if (!s || !t) return "";
  const need = new Map();
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
  const required = need.size;            // t-এর আলাদা অক্ষরের সংখ্যা
  const window = new Map();
  let formed = 0, left = 0;
  let bestLen = Infinity, bestLeft = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    window.set(ch, (window.get(ch) || 0) + 1);
    if (need.has(ch) && window.get(ch) === need.get(ch)) formed++;  // ঠিক চাহিদায়
    while (formed === required) {         // window valid -> ছোট করো
      if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestLeft = left; }
      const lc = s[left];
      window.set(lc, window.get(lc) - 1);
      if (need.has(lc) && window.get(lc) < need.get(lc)) formed--;  // valid ভাঙল
      left++;
    }
  }
  return bestLen === Infinity ? "" : s.slice(bestLeft, bestLeft + bestLen);
}
// ---- test cases (example + edge) ----
assert(minWindow("ADOBECODEBANC", "ABC") === "BANC", "classic");
assert(minWindow("a", "a") === "a", "single");
assert(minWindow("a", "aa") === "", "not-enough");               // edge
assert(minWindow("", "a") === "", "empty-s");                    // edge
console.log("সব JS test pass!");

JS টীকা: window.get(ch) === need.get(ch) (ঠিক সমান হলে formed++), >= নয় — নাহলে একই অক্ষর বহুবার গোনা হবে। substring বের করতে s.slice(start, end); "এখনো পাইনি" বোঝাতে Infinity।

TypeScript ও test cases

TypeScript

function minWindow(s: string, t: string): string {
  if (!s || !t) return "";
  const need = new Map<string, number>();
  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
  const required: number = need.size;
  const window = new Map<string, number>();
  let formed = 0, left = 0;
  let bestLen: number = Infinity, bestLeft = 0;
  for (let right = 0; right < s.length; right++) {
    const ch: string = s[right];
    window.set(ch, (window.get(ch) ?? 0) + 1);
    if (need.has(ch) && window.get(ch) === need.get(ch)) formed++;
    while (formed === required) {
      if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestLeft = left; }
      const lc: string = s[left];
      window.set(lc, (window.get(lc) ?? 0) - 1);
      if (need.has(lc) && (window.get(lc) ?? 0) < (need.get(lc) ?? 0)) formed--;
      left++;
    }
  }
  return bestLen === Infinity ? "" : s.slice(bestLeft, bestLeft + bestLen);
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(minWindow("ADOBECODEBANC", "ABC"), "BANC", "classic");
expect(minWindow("a", "aa"), "", "not-enough");
expect(minWindow("", "a"), "", "empty-s");
console.log("সব TS test pass!");

TS টীকা: Map<string, number> typed get দেয় number | undefined, তাই ?? 0 দিয়ে count compare করা compiler-enforced; formed counter-এর তুলনা সব number-এ হওয়ায় valid-check নিরাপদ।

খরচ ও সাধারণ ভুল

সময়

O(|s| + |t|) — t গুনতে O(|t|); right ও left দুটোই s-এর উপর শুধু সামনে চলে, প্রতিটা index একবার ঢোকে একবার বের হয়, প্রতিটা step O(1)।

অতিরিক্ত জায়গা

O(k) — need ও window map-এ বড়জোর k আলাদা অক্ষর (character set-এর আকার, যেমন ASCII হলে কার্যত O(1))।

যে ভুলগুলো এড়াতে হবে

• formed counter না রেখে প্রতিবার পুরো need map স্ক্যান করে valid কিনা দেখা — তখন প্রতি step-এ O(k), পুরো সৌকর্য নষ্ট।
• window[ch] == need[ch]-এর বদলে >= দিয়ে formed বাড়ানো — তখন একই অক্ষর বহুবার formed বাড়িয়ে গোনা ভুল করে।
• valid হওয়ার পর shrink না করা — তখন সবচেয়ে ছোট নয়, যেকোনো একটা valid পাও।
• best দৈর্ঘ্য না রেখে best string বারবার slice/compare করা — কাজ করে, কিন্তু অপ্রয়োজনীয় copy; index রাখাই সস্তা।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: variable-size sliding window (Longest Unique Substring #10) + frequency counting (Valid Anagram #3)। এখানে নতুন মোচড় হলো shrinkable window — valid বানিয়ে minimal করা। chapter-এর ../patterns.md-এর "Pattern 2 — Sliding Window" দেখো।

পরের অনুশীলন

• Longest Substring Without Repeating Characters (ভিত্তি window) — https://leetcode.com/problems/longest-substring-without-repeating-characters/ (#10)
• Permutation in String (fixed-size window + count) — https://leetcode.com/problems/permutation-in-string/
• Substring with Concatenation of All Words — https://leetcode.com/problems/substring-with-concatenation-of-all-words/

কৌশলটি মনে রাখুন

Shrinkable sliding window: "সবচেয়ে ছোট window যা শর্ত মেটায়" দেখলে ডান প্রান্ত দিয়ে expand-to-valid, তারপর বাঁ প্রান্ত দিয়ে shrink-to-minimal করো; formed counter দিয়ে O(1)-এ valid যাচাই — মোট O(n)।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "minimum window = expand করে valid বানাও, তারপর left চেপে যতটা পারো ছোট করো; formed==required মানে valid।" "সব char ধরে এমন shortest substring" দেখলেই shrinkable sliding window + count মনে করবে — O(|s|+|t|) time।

কোথায় কাজে লাগে

• Search snippet generation: কোনো document-এ সব query term ধরে এমন সবচেয়ে ছোট passage বের করা (minimal covering window)।
• Log forensics: নির্দিষ্ট সব event ঘটেছে এমন সবচেয়ে ছোট সময়-উইন্ডো খোঁজা।
• DNA/sequence: সব দরকারি marker ধরে রাখা সবচেয়ে ছোট segment।
• Ad/coverage: সব required tag/feature ঢাকা সবচেয়ে ছোট span।
• Network trace: সব handshake step সম্পন্ন হওয়া ন্যূনতম packet-window।
• Recommendation bundling: সব চাহিদা পূরণ করা সবচেয়ে ছোট item-set window।

মূল pattern: ডান প্রান্তে expand করে valid বানাও, বাঁ প্রান্তে shrink করে minimal; formed === required দিয়ে O(1) valid-check — "সব ধরে এমন shortest" দেখলেই shrinkable window।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।