020 — Minimum Window Substring¶

Source¶

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

1. Problem in simple words¶

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

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

2. Which basic idea does this inherit from?¶

ভিত হলো 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/।

3. What is the hidden math or logic?¶

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

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

s = "ADOBECODEBANC", t = "ABC" — expand করে valid, তারপর shrink:

expand R: A D O B E C  -> window "ADOBEC" সব A,B,C ধরা (valid)
shrink L: 'A' ফেললে A কমে invalid -> থামো; best = "ADOBEC" (6)
...R এগোয়, আবার A আসে index 10 -> valid; shrink করে "ANC"? না, "CODEBA" থেকে...
শেষমেশ R 'C'(index 12)-এ valid; shrink করে "BANC" (4) -> সবচেয়ে ছোট

answer: "BANC"

8. Example input and 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"  -> ""

9. Brute force thinking¶

প্রথম সরল চিন্তা: 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])

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

need = {a:1}, required = 1, formed = 0, left = 0, best_len = ∞।
right=0 'a': window={a:1}; a need-এ আর window[a]==need[a] → formed=1।
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 শেষ।
right শেষ। best_len=1 → s[0:1] = "a"।

15. Python solution¶

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

16. Line-by-line code explanation¶

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 স্লাইস।

17. Output walkthrough¶

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

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

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/

23. Pattern learned¶

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

24. Final summary¶

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

25. JavaScript solution (with test cases)¶

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

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।

26. TypeScript solution (with test cases)¶

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 নিরাপদ।

27. কোথায় কাজে লাগে (real-world use)¶

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।