Skip to content

023 — Minimum Window Substring

Source

  • Original source: Classic sliding-window covering interview problem
  • Platform: LeetCode — https://leetcode.com/problems/minimum-window-substring/
  • Topic: strings + hashing
  • Difficulty: Hard
  • Pattern: Sliding window + counting hashmap
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 02 strings (একটা string-এর উপর দুটো pointer দিয়ে window স্লাইড করা) আর 05 hashing (window-এর ভেতরে কোন character কয়টা আছে, আর কয়টা দরকার, সেটা count করা)। দুটো জোড়া লাগলেই O(n) covering window।

1. Problem in simple words

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

s = "ADOBECODEBANC", t = "ABC"
সবচেয়ে ছোট covering window : "BANC"   (A,B,C তিনটাই আছে)
উত্তর : "BANC"

2. Which basic idea does this inherit from?

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

  • 02 strings (../../02-arrays-and-strings/) থেকে: একটা string-এর উপর দুটো index (left, right) দিয়ে একটা চলন্ত window — ডান প্রান্ত বাড়াও, বাঁ প্রান্ত গুটাও।
  • 05 hashing (../../05-hashing/) থেকে: দুটো frequency map — need (t-তে কোন char কয়টা) আর window-এর running count — যাতে O(1)-এ বলা যায় "window কি সব দরকারি char ঢেকেছে?"

একা sliding window দেয় "কোথায়" দেখার গতি; একা hashmap দেয় "ভেতরে কী আছে" জানার গতি। দুটো মিললে O(n)।

3. What is the hidden math or logic?

লুকানো logic একটা monotone feasibility: window যত বড় হয়, "সব char ঢাকা" property তত সহজে সত্যি — তাই ডান প্রান্ত বাড়িয়ে feasible বানাও, তারপর বাঁ প্রান্ত গুটিয়ে সবচেয়ে ছোট feasible খোঁজো।

মূল trick একটা have == need counter: need = t-র distinct char সংখ্যা যেগুলোর count পূর্ণ হতে হবে; have = এই মুহূর্তে window-এ কতগুলো char তাদের দরকারি count ছুঁয়েছে। have == need মানেই window valid — প্রতিবার পুরো map তুলনা না করে O(1)-তে জানা।

4. Which data structure is needed?

দরকার: (a) একটা count dict need (t-র character frequency), (b) একটা count dict window (বর্তমান window-এর frequency), আর দুটো integer pointer (left, right) string scan-এর জন্য (02)। সাথে have/need দুটো counter valid-check O(1) রাখতে।

5. Why this data structure fits

sliding window (02) দেয় single linear sweep — প্রতিটা index বড়জোর দুবার ছোঁয়া (একবার right, একবার left), তাই O(n)। hashmap (05) দেয় constant-time count আপডেট আর "ঢাকা হয়েছে কি" check। array দিয়েও (যদি charset ছোট, যেমন ASCII 128) করা যায়, কিন্তু hashmap general charset-এ পরিষ্কার। প্রতিবার substring বের করে t-র সাথে মেলানো O(n) করত প্রতি window-এ — hashmap সেটা O(1) incremental আপডেটে নামায়।

6. Real-life analogy

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

7. Visual explanation

s = A D O B E C O D E B A N C ,  t = ABC  (need: A1,B1,C1)

right বাড়াও যতক্ষণ window valid নয়:
[A D O B E C] -> A,B,C ঢাকা! valid, length 6
বাঁ গুটাও যতক্ষণ valid থাকে:
 A বাদ -> (A D O B E C](=DOBEC) আর A নেই -> invalid, থামো; best=ADOBEC(6)

right আরও বাড়াও ...শেষে window পৌঁছায়:
... B A N C  -> A,B,C ঢাকা, length 4 < 6 -> best = "BANC"
উত্তর : BANC

8. Example input and output

Input : s="ADOBECODEBANC", t="ABC"
Output: "BANC"

Edge case 1 (কোনো cover নেই): s="a", t="aa" -> ""        # দুটো a লাগে, একটা আছে
Edge case 2 (পুরোটাই answer): s="a", t="a"  -> "a"
Edge case 3 (duplicate target): s="aa", t="aa" -> "aa"   # multiplicity মানতে হয়

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য (start, end) substring ধরো, চেক করো এতে t-র সব char (count সহ) আছে কি না, valid হলে length দেখে সবচেয়ে ছোটটা মনে রাখো।

best = ""
for i in range(n):
    for j in range(i, n):
        if covers(s[i..j], t):       # প্রতিবার count মিলিয়ে দেখা
            update best if shorter

10. Why brute force is slow

দুটো nested loop সব substring (O(n²)), আর প্রতিটায় covers চেক O(n+|t|) — মোট O(n³) (বা count cache করলে O(n²·alphabet))। বড় s-তে ধীর। কারণ একটা window থেকে পরের window-এ গেলে count প্রায় একই থাকে, তবু আমরা প্রতিবার শূন্য থেকে গুনছি — sliding window + hashmap (02+05) এই reuse এনে O(n) করে।

11. Key observation

মূল observation: window valid হওয়া monotone — একবার valid হলে ডান বাড়ালেও valid থাকে। তাই সব substring দেখার দরকার নেই: ডান বাড়িয়ে প্রথম valid বানাও, তারপর যত পারো বাঁ গুটিয়ে সংকুচিত করো; আবার ডান বাড়াও। প্রতিটা index মাত্র দুবার ছোঁওয়া হয়। আর have==need counter দিয়ে validity O(1)-তে জানা যায়, full-map তুলনা ছাড়া।

12. Optimized intuition

need = t-র char count; required = distinct char সংখ্যা যাদের count পূরণ করতে হবে। right বাড়িয়ে char যোগ করো, count পূর্ণ হলে have += 1। যখন have == required, window valid — এখন left বাড়িয়ে যত পারো ছোটো করো (best আপডেট করতে করতে), যতক্ষণ না কোনো char-এর count দরকারের নিচে নামে (have -= 1)। তারপর আবার right এগোও। শেষে সবচেয়ে ছোট valid window-ই উত্তর।

13. Thinking tweak

মোচড়: "সব substring দেখব" ভাবা ছাড়ো। ভাবো "একটা elastic window — feasible না হওয়া পর্যন্ত ডানে টানো, তারপর feasible থাকা পর্যন্ত বাঁয়ে চাপো।" বিশাল O(n²) search একটা two-pointer O(n) sweep-এ পরিণত হয়, hashmap শুধু "ঢাকা হলো কি" বলে দেয়।

14. Step-by-step dry run

s="ADOBEC...", t="ABC" (need: A1,B1,C1; required=3):

  1. right এগোয়: A(have→1, A ঢাকা), D, O, B(have→2), E, C(have→3 = required) → valid; window "ADOBEC", best="ADOBEC"(6)
  2. left গুটায়: A বাদ → A-count 0 < 1, have→2, থামো (invalid)
  3. right এগোয়: ...O,D,E,B,A,N,C ঘুরে আবার A,B,C ঢাকা; window সংকুচিত করতে করতে
  4. শেষে valid window "BANC" (length 4) < 6 → best="BANC"
  5. scan শেষ → return "BANC"

15. Python solution

from collections import Counter

def min_window(s, t):
    if not s or not t or len(t) > len(s):
        return ""
    need = Counter(t)                    # 05 hashing: কোন char কয়টা দরকার
    required = len(need)                 # কতগুলো distinct char পূরণ করতে হবে
    window = {}                          # বর্তমান window-এর count
    have = 0                             # কয়টা char তাদের দরকার ছুঁয়েছে
    best_len = float("inf")
    best_l = 0
    left = 0
    for right, ch in enumerate(s):       # 02 strings: ডান প্রান্ত বাড়াও
        window[ch] = window.get(ch, 0) + 1
        if ch in need and window[ch] == need[ch]:
            have += 1
        while have == required:          # valid -> বাঁ গুটিয়ে ছোটো করো
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_l = left
            lch = s[left]
            window[lch] -= 1
            if lch in need and window[lch] < need[lch]:
                have -= 1                # একটা char দরকারের নিচে নামল
            left += 1
    return "" if best_len == float("inf") else s[best_l:best_l + best_len]

# ---- tests ----
assert min_window("ADOBECODEBANC", "ABC") == "BANC"
assert min_window("a", "aa") == ""           # দুটো a লাগে
assert min_window("a", "a") == "a"
assert min_window("aa", "aa") == "aa"        # multiplicity
assert min_window("ab", "b") == "b"
assert min_window("cabwefgewcwaefgcf", "cae") == "cwae"
print("সব test pass!")

16. Line-by-line code explanation

  • if not s or not t or len(t) > len(s): return "" — অসম্ভব cases আগেই বাদ।
  • need = Counter(t) / required = len(need) — target-এর char frequency আর কয়টা distinct char পূরণ করতে হবে (05 hashing)।
  • for right, ch in enumerate(s) — ডান প্রান্ত একধাপ বাড়িয়ে window-এ char যোগ (02 strings)।
  • if ch in need and window[ch] == need[ch]: have += 1 — কোনো char ঠিক দরকারি count ছুঁলে valid-counter বাড়ে।
  • while have == required — window valid; এখন best আপডেট করে বাঁ প্রান্ত গুটিয়ে সংকুচিত করি।
  • if lch in need and window[lch] < need[lch]: have -= 1 — বাঁ char সরিয়ে কোনো char দরকারের নিচে নামলে আর valid না।
  • return ... — কখনো valid না হলে "", নাহলে best window-এর slice।

17. Output walkthrough

s="ADOBECODEBANC"-এ right বাড়িয়ে প্রথম valid "ADOBEC"(6), তারপর scan চলতে চলতে "BANC"(4) সবচেয়ে ছোট valid → return "BANC"; assert pass। s="a",t="aa" এ কখনো have==required হয় না → ""; "aa","aa" এ multiplicity ঢাকে → "aa"; অন্যগুলোও সঠিক। শেষে print: সব test pass!।

18. Time complexity

O(|s| + |t|) — t গুনতে O(|t|); s-এর প্রতিটা index right-এ একবার, left-এ একবার ছোঁয়া (amortized), প্রতি step O(1) hashmap কাজ।

19. Space complexity

O(|t| + k) — need map t-র distinct char ধরে, window map বড়জোর distinct char (k) ধরে; charset সীমিত হলে O(1)।

20. Common mistakes

  • প্রতিবার পুরো window আর need map তুলনা করে validity দেখা — O(alphabet) প্রতি step; have==required counter দিয়ে O(1) করো।
  • have বাড়ানোর শর্ত >= লেখা (window[ch] >= need[ch]) — তাহলে একই char বারবার have বাড়ায়, ভুল; == দিয়ে ঠিক একবার গোনো।
  • multiplicity উপেক্ষা করা (t-তে duplicate char) — শুধু "present কি না" দেখলে "aa" target-এ একটা a-কে যথেষ্ট ভাবে; count মেলাও।
  • best window-এর start/length না রেখে শুধু length রাখা — তখন substring ফেরত দিতে পারবে না; best_l রাখো।

21. Which basic problem this inherits from

ভিত্তি: two-pointer sliding window over a string (02-এর ../../02-arrays-and-strings/) + frequency hashmap দিয়ে O(1) count/coverage check (05 hashing-এর ../../05-hashing/)। এই দুটো cold অবস্থায় জানা থাকলে minimum window নিজে থেকেই দাঁড়ায়। (../hard-patterns.md-এর combo 2।)

22. Similar harder problems

23. Pattern learned

Sliding window + counting hashmap: দুটো pointer সামলায় window কোথায়, একটা count map সামলায় ভেতরে কী আছে। ডান বাড়িয়ে feasible বানাও, বাঁ গুটিয়ে minimal বানাও, have==need counter দিয়ে validity O(1) রাখো। "shortest/longest substring satisfying a count condition" problem-এর canonical রূপ।

24. Final summary

ভবিষ্যতের আমাকে: "সব char ঢাকা সবচেয়ে ছোট/বড় substring" শুনলেই sliding window + count map মনে করবে। need map বানাও, ডান বাড়িয়ে have==required হওয়া পর্যন্ত expand করো, তারপর বাঁ গুটিয়ে best আপডেট করো। validity-র জন্য পুরো map না মিলিয়ে counter রাখো, multiplicity মানো, আর best-এর start+length দুটোই রাখো। এটা strings + hashing-এর পরিষ্কার মেলবন্ধন।

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