Problem link ও উৎস
- **Original source:** Classic sliding-window covering interview problem
- **Platform:** LeetCode —
- **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।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে দুটো string দেওয়া আছে: `s` (বড়টা) আর `t` (target)। `s`-এর এমন **সবচেয়ে ছোট পরপর থাকা টুকরো (substring)** খুঁজে বের করো, যার ভেতরে `t`-র **সব character** আছে — আর duplicate থাকলে যথেষ্ট সংখ্যায় আছে (multiplicity সহ)। এমন কোনো window না থাকলে খালি string `""` ফেরত দাও।
```text
s = "ADOBECODEBANC", t = "ABC"
সবচেয়ে ছোট covering window : "BANC" (A,B,C তিনটাই আছে)
উত্তর : "BANC"
```
### Input ও output {#8-example-input-and-output}
```text
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 মানতে হয়
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তোমার একটা shopping list আছে (t)। তুমি একটা লম্বা তাকের সামনে দিয়ে ডান দিকে হাঁটছ (right বাড়ছে), ঝুড়িতে জিনিস তুলছ — যখন list-এর সব জিনিস ঝুড়িতে এসে গেল, থামো। এখন বাঁ দিক থেকে অপ্রয়োজনীয় জিনিস ফেরত রাখতে থাকো (left বাড়ছে) যতক্ষণ list ঢাকা থাকে — সবচেয়ে ছোট তাক-অংশটাই তোমার উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **02 strings** ([../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)) থেকে: একটা string-এর উপর দুটো index (`left`, `right`) দিয়ে একটা চলন্ত window — ডান প্রান্ত বাড়াও, বাঁ প্রান্ত গুটাও।
- **05 hashing** ([../../05-hashing/](../../05-hashing/README.md)) থেকে: দুটো 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 আপডেটে নামায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য (start, end) substring ধরো, চেক করো এতে t-র সব char (count সহ) আছে কি না, valid হলে length দেখে সবচেয়ে ছোটটা মনে রাখো।
```text
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 শুধু "ঢাকা হলো কি" বলে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
`s="ADOBECODEBANC"`, `t="ABC"`। Index 0 থেকে। Valid window-তে A, B ও C প্রত্যেকটি অন্তত একবার চাই। নিচে right-এর প্রতিটি অবস্থার ফল আছে; valid হলেই left যতদূর সম্ভব এগোয়।
| right | নতুন char | সংকোচনের আগে window | সংকোচনের কাজ | best |
| --- | --- | --- | --- | --- |
| 0 | A | A | B,C নেই | নেই |
| 1 | D | AD | B,C নেই | নেই |
| 2 | O | ADO | B,C নেই | নেই |
| 3 | B | ADOB | C নেই | নেই |
| 4 | E | ADOBE | C নেই | নেই |
| 5 | C | ADOBEC | Length 6 রাখুন; A বাদে invalid, left=1 | ADOBEC |
| 6 | O | DOBECO | A নেই | ADOBEC |
| 7 | D | DOBECOD | A নেই | ADOBEC |
| 8 | E | DOBECODE | A নেই | ADOBEC |
| 9 | B | DOBECODEB | A নেই | ADOBEC |
| 10 | A | DOBECODEBA | D,O,B,E বাদ; CODEBA length 6; C বাদে invalid, left=6 | ADOBEC |
| 11 | N | ODEBAN | C নেই | ADOBEC |
| 12 | C | ODEBANC | O,D,E বাদ; BANC length 4 রাখুন; B বাদে invalid | BANC |
শেষ উত্তর `BANC`। Target-এ duplicate থাকলে শুধু distinct character উপস্থিতি যথেষ্ট নয়; প্রতিটির required count পূরণ করতে হবে।
### ছোট input-এ ধাপে ধাপে {#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"
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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` রাখো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: two-pointer sliding window over a string (02-এর [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)) + frequency hashmap দিয়ে O(1) count/coverage check (05 hashing-এর [../../05-hashing/](../../05-hashing/README.md))। এই দুটো cold অবস্থায় জানা থাকলে minimum window নিজে থেকেই দাঁড়ায়। ([../hard-patterns.md](../hard-patterns.md)-এর combo 2।)
### পরের অনুশীলন {#22-similar-harder-problems}
- Substring with Concatenation of All Words (window + word-count map, এক ধাপ কঠিন) —