কনটেন্টে যান

020 — Minimum Window Substring

Problem link ও উৎস

  • 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 দিয়ে সংকোচন

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

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

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

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

Input ও 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 খালি)

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

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

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

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

দুটো ভিত্তির সংকর। প্রথমটা 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 বাড়াও যতক্ষণ না সব অক্ষর ঢাকা পড়ে, তারপর বাঁ দিক টেনে ছোট করো।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ছবিতে বোঝা

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 = "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"।

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

Python

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

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

  • 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 থামে।

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

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

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

সময়

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

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

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

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

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

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

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

ভিত্তি: 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 সংস্করণসহ)।

পরের অনুশীলন

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

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

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

ভবিষ্যতের আমাকে: "এমন সবচেয়ে ছোট/বড় 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।