Skip to content

020 — Minimum Window Substring

Source

  • Original source: Classic frequency-counting + sliding-window exercise
  • Platform: LeetCode — https://leetcode.com/problems/minimum-window-substring/
  • Topic: hash map (counts) + sliding window
  • Difficulty: Hard
  • Pattern: frequency counting + sliding window
  • Basic idea inherited from: Valid Anagram counts + arrays section-এর window — count দিয়ে "ঢাকা পড়েছে কি" মাপা, window দিয়ে সংকোচন

1. Problem in simple words

দুটো string s আর t দেওয়া আছে। s-এর মধ্যে এমন সবচেয়ে ছোট পরপর টুকরো (window) বের করতে হবে যেটায় t-র সব অক্ষর (পুনরাবৃত্তি সহ — t-তে দুটো 'a' থাকলে window-তেও অন্তত দুটো 'a') আছে। এমন কোনো window না থাকলে খালি string ফেরত দাও।

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

2. Which basic idea does this inherit from?

দুটো ভিত্তির সংকর। প্রথমটা frequency counting (Pattern 1, Valid Anagram #3-এর আত্মীয়) — t-র প্রতিটা অক্ষর কতবার লাগবে তা গোনা, আর window-তে কতবার আছে তা মেলানো। দ্বিতীয়টা sliding window — math fundamentals-এর ../../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/-এ শেখা দুই-pointer সংকোচন/সম্প্রসারণ। দুটো মিলে: window বাড়াও যতক্ষণ না সব অক্ষর ঢাকা পড়ে, তারপর বাঁ দিক টেনে ছোট করো।

3. What is the hidden math or logic?

লুকানো logic: "সব অক্ষর ঢাকা পড়েছে কি না" পুরো count মিলিয়ে বারবার যাচাই করা ব্যয়বহুল। বদলে একটা সংখ্যা have রাখো — কয়টা distinct অক্ষরের চাহিদা এখন পুরোপুরি মিটেছে — আর required হলো t-র distinct অক্ষরের সংখ্যা। have == required মানেই পুরো t ঢাকা পড়েছে। তাই প্রতি ধাপে O(distinct) যাচাই নেমে আসে O(1) তুলনায়। এটাই সংকোচনকে দক্ষ করে।

4. Which data structure is needed?

দুটো hash map / Counter: need (t-র char → কতবার লাগবে) আর window (এখনকার window-তে char → কতবার আছে)। সাথে দুটো integer: required (= distinct char in t) আর have (এখন কতগুলো distinct char-এর চাহিদা পুরো)। দুটো pointer left, right window-এর সীমা।

5. Why this data structure fits

need আর window count ধরে রাখে বলে আমরা পুনরাবৃত্ত অক্ষরও (যেমন t = "AABC"-তে দুটো A) ঠিকঠাক সামলাই — শুধু "আছে কি নেই" set দিয়ে হতো না। hash map-এ count update আর lookup গড়ে O(1)। have/required কৌশলে প্রতি ধাপে "সম্পূর্ণ ঢাকা?" check-ও O(1)। ফলে দুই pointer মিলিয়ে প্রতিটা অক্ষর সর্বোচ্চ দুবার ছোঁয়া — মোট O(|s|)।

6. Real-life analogy

ভাবো একটা রেসিপির জন্য বাজার করছ: লাগবে 2টা ডিম, 1টা দুধ, 1টা মাখন (এটাই need)। তুমি একটা থলিতে জিনিস ঢোকাচ্ছ (window বাড়ছে) যতক্ষণ না পুরো রেসিপি ঢাকা পড়ে। ঢাকা পড়লে এবার থলির শুরুর দিক থেকে অপ্রয়োজনীয় জিনিস বের করতে থাকো (বাঁ দিক টানা) — যতক্ষণ থলি বৈধ থাকে। সবচেয়ে হালকা বৈধ থলিটাই উত্তর। প্রতিটা জিনিস একবার ঢোকে, একবার বেরোয়।

7. Visual explanation

s = "ADOBEC", t = "ABC"; need = {A:1, B:1, C:1}, required = 3। right বাড়ে, সব ঢাকা পড়লে left টানি:

right→A  window{A:1}            have=1
right→D  window{A:1,D:1}        have=1
right→O  ...                    have=1
right→B  window{A,D,O,B}        have=2
right→E  ...                    have=2
right→C  window{...,C:1}        have=3 == required!
   শুরু "ADOBEC" বৈধ; left টানি: A বেরোলে have=2 → থামো
   এই মুহূর্তের সেরা window: "ADOBEC" (length 6)

বড় string-এ এভাবেই আরও ছোট বৈধ window পাওয়া যায় (যেমন আসল উদাহরণে "BANC")।

8. Example input and output

Input : s = "ADOBECODEBANC", t = "ABC"    Output: "BANC"
Input : s = "a", t = "a"                   Output: "a"
Input : s = "a", t = "aa"                  Output: ""    (দুটো a নেই)
Input : s = "ab", t = "b"                  Output: "b"
Input : s = "",  t = "a"                   Output: ""    (s খালি)

9. Brute force thinking

প্রথম সরল চিন্তা: s-এর প্রতিটা substring (প্রতিটা শুরু-শেষ জোড়া) ধরে দেখো t-র সব অক্ষর আছে কি না, আর সবচেয়ে ছোট বৈধটা রাখো।

সবচেয়ে ছোট = অসীম
প্রতিটা শুরু i-র জন্য:
    প্রতিটা শেষ j >= i-র জন্য:
        s[i..j]-এ t-র সব অক্ষর (count সহ) আছে?
        থাকলে দৈর্ঘ্য সবচেয়ে ছোটের সাথে তুলনা করো

10. Why brute force is slow

substring-এর সংখ্যা O(n^2), আর প্রতিটায় count যাচাই আরও O(n) — মোট প্রায় O(n^3) (বা সাবধানে O(n^2))। অপচয়টা: একটা শুরু থেকে window বাড়ালে পুরোনো count পুনর্ব্যবহার করা যায়, কিন্তু brute force প্রতিবার শূন্য থেকে গোনে। দুই pointer সেই count কে incremental রাখে — তাই এক pass-এ নেমে আসে।

11. Key observation

মূল observation: একটা বৈধ window পেলে, বাঁ দিক যতটা টানা যায় ততই ছোট ও ভালো — যতক্ষণ না বৈধতা ভাঙে। আর "বৈধ?" check টাকে have == required দিয়ে O(1) করা যায়। তাই দুই pointer একদিকে এগোয়, কখনো পিছায় না — প্রতিটা অক্ষর সর্বোচ্চ দুবার ছোঁয়া হয়।

12. Optimized intuition

need = Counter(t), required = len(need)। right দিয়ে window বাড়াও; কোনো needed char-এর count ঠিক চাহিদায় পৌঁছালে have += 1। have == required হলে ভেতরের while-এ ঢুকে: এখনকার window সেরার চেয়ে ছোট হলে নথিভুক্ত করো, তারপর বাঁ অক্ষর বের করে left বাড়াও; বাঁ অক্ষর needed হলে আর তার count চাহিদার নিচে নামলে have -= 1 (window আবার অবৈধ, while ভাঙে)। শেষে সেরা window ফেরত। O(|s| + |t|)।

13. Thinking tweak

মোচড়: পুরো count বারবার মিলিও না — একটা have/required counter দিয়ে "ঢাকা পড়েছে?" O(1)-এ মাপো, আর window বৈধ থাকতে থাকতে বাঁ দিক টেনে ছোট করো। "expand তারপর contract" — এই দুই-পর্যায়ের sliding window হলো প্রায় সব "minimum/maximum window with condition" problem-এর মেরুদণ্ড।

14. Step-by-step dry run

Input s = "ab", t = "b"; need = {b:1}, required = 1, have = 0, সেরা = অসীম।

  1. right=0, ch='a': window = {a:1}; 'a' needed নয় → have = 0।
  2. right=1, ch='b': window = {a:1, b:1}; window[b] == need[b] → have = 1।
  3. have == required → window s[0:2] = "ab" (length 2) সেরা; বাঁ অক্ষর 'a' বের, left=1, 'a' needed নয় → have অটুট।
  4. আবার have == required → window s[1:2] = "b" (length 1) আরও ছোট, সেরা হলো; বাঁ অক্ষর 'b' বের, window[b]=0 < 1 → have = 0, left=2।
  5. উত্তর: "b"।

15. Python solution

from collections import Counter

def min_window(s, t):
    if not s or not t:
        return ""
    need = Counter(t)                       # char -> কতবার লাগবে
    required = len(need)                     # কয়টা distinct char পুরো হতে হবে
    have = 0                                 # এখন কয়টা distinct char পুরো
    window = {}                              # window-এর char -> count
    best_len = float("inf")
    best_left = 0
    left = 0
    for right, ch in enumerate(s):
        window[ch] = window.get(ch, 0) + 1
        if ch in need and window[ch] == need[ch]:
            have += 1
        while have == required:             # সব ঢাকা পড়েছে → বাঁ দিক টানো
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_left = left
            lch = s[left]
            window[lch] -= 1
            if lch in need and window[lch] < need[lch]:
                have -= 1                    # বৈধতা ভাঙল
            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("ab", "b") == "b"
assert min_window("", "a") == ""            # s খালি
print("সব test pass!")

16. Line-by-line code explanation

  • if not s or not t: return "" — খালি input-এ বৈধ window অসম্ভব।
  • need = Counter(t); required = len(need) — চাহিদার count আর কয়টা distinct char পুরো হতে হবে।
  • have = 0; window = {} — এখন কয়টা char-এর চাহিদা পুরো, আর window-এর running count।
  • for right, ch in enumerate(s) — right দিয়ে window সম্প্রসারণ।
  • if ch in need and window[ch] == need[ch]: have += 1 — এই char-এর চাহিদা ঠিক পূর্ণ হলো (বেশি হলে আর গোনা নয়)।
  • while have == required — পুরো t ঢাকা; এখন বাঁ দিক টেনে সংকুচিত করো।
  • if right - left + 1 < best_len — আরও ছোট বৈধ window পেলে নথিভুক্ত করো।
  • window[lch] -= 1; if ... window[lch] < need[lch]: have -= 1 — বাঁ অক্ষর বাদ দিয়ে যদি চাহিদা ভাঙে, have কমাও, while থামে।

17. Output walkthrough

"ADOBECODEBANC", "ABC"-এ window বড় হয়ে সব ঢাকা পড়ার পর বাঁ দিক টেনে শেষমেশ সবচেয়ে ছোট বৈধ window "BANC" মেলে। "a","a"-তে এক অক্ষরেই ঢাকা → "a"। "a","aa"-তে কখনো দুটো a জোগাড় হয় না → have কখনো required ছোঁয় না → ""। "ab","b"-তে "b"। খালি s-এ শুরুতেই ""। শেষে print: সব test pass!।

18. Time complexity

O(|s| + |t|) — t গুনতে O(|t|); দুই pointer s-এর উপর, প্রতিটা অক্ষর সর্বোচ্চ একবার right-এ ঢোকে, একবার left-এ বেরোয়, প্রতিবার O(1) hash কাজ।

19. Space complexity

O(|s| + |t|) — need-এ t-র distinct char, window-এ window-এর distinct char।

20. Common mistakes

  • পুনরাবৃত্ত অক্ষর ভুল সামলানো — set দিয়ে করলে t = "AABC"-এর দুটো A ধরা পড়ে না; count (Counter) লাগবে।
  • have বাড়ানো/কমানোর শর্তে ==/< গুলিয়ে ফেলা — বাড়াও ঠিক যখন window[ch] == need[ch] (বেশি হলে নয়), কমাও যখন বের করার পর window[lch] < need[lch]।
  • সংকোচনের সময় সেরা window নথিভুক্ত করার আগেই left টেনে ফেলা — আগে দৈর্ঘ্য তুলনা করে রাখো, পরে অক্ষর বের করো।

21. Which basic problem this inherits from

ভিত্তি: frequency counting (Pattern 1, Valid Anagram #3) — count দিয়ে "ঢাকা পড়েছে?" মাপা — আর math fundamentals-এর sliding window (../../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/)। এই note দেখায় দুটো chapter-এর idea মিশে কীভাবে একটা hard string problem সারে। সম্পূর্ণ আলোচনা ../patterns.md-র Pattern 1-এ (window সংস্করণসহ)।

22. Similar harder problems

23. Pattern learned

Frequency counting + sliding window: need count আর have/required দিয়ে "সব ঢাকা পড়েছে?" O(1)-এ মাপো; right দিয়ে বাড়াও, বৈধ হলে left দিয়ে ছোট করো — "expand তারপর contract", এক pass O(|s|)।

24. Final summary

ভবিষ্যতের আমাকে: "এমন সবচেয়ে ছোট/বড় substring/window যেটায় শর্ত X মেটে" শুনলেই দুই-pointer sliding window + count মনে পড়বে। মূল কৌশল — পুরো count বারবার মিলিও না, have/required দিয়ে O(1)-এ বৈধতা মাপো; বৈধ হলেই বাঁ দিক টেনে ছোট করো। এই hard problem আসলে Valid Anagram-এর count + arrays-এর window, একসাথে।

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