Problem link ও উৎস
- **Original source:** Classic frequency-counting + sliding-window exercise
- **Platform:** LeetCode —
- **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 দিয়ে সংকোচন
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো string `s` আর `t` দেওয়া আছে। `s`-এর মধ্যে এমন সবচেয়ে **ছোট পরপর টুকরো (window)** বের করতে হবে যেটায় `t`-র **সব অক্ষর** (পুনরাবৃত্তি সহ — `t`-তে দুটো `'a'` থাকলে window-তেও অন্তত দুটো `'a'`) আছে। এমন কোনো window না থাকলে খালি string ফেরত দাও।
```text
s = "ADOBECODEBANC", t = "ABC"
সবচেয়ে ছোট window যেটায় A, B, C সব আছে: "BANC"
উত্তর: "BANC"
```
### Input ও output {#8-example-input-and-output}
```text
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 খালি)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা রেসিপির জন্য বাজার করছ: লাগবে 2টা ডিম, 1টা দুধ, 1টা মাখন (এটাই `need`)। তুমি একটা থলিতে জিনিস ঢোকাচ্ছ (window বাড়ছে) যতক্ষণ না পুরো রেসিপি ঢাকা পড়ে। ঢাকা পড়লে এবার থলির শুরুর দিক থেকে অপ্রয়োজনীয় জিনিস বের করতে থাকো (বাঁ দিক টানা) — যতক্ষণ থলি বৈধ থাকে। সবচেয়ে হালকা বৈধ থলিটাই উত্তর। প্রতিটা জিনিস একবার ঢোকে, একবার বেরোয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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/](../../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/README.md)-এ শেখা দুই-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|)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: `s`-এর প্রতিটা substring (প্রতিটা শুরু-শেষ জোড়া) ধরে দেখো `t`-র সব অক্ষর আছে কি না, আর সবচেয়ে ছোট বৈধটা রাখো।
```text
সবচেয়ে ছোট = অসীম
প্রতিটা শুরু 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-এর মেরুদণ্ড।
### ছবিতে বোঝা {#7-visual-explanation}
`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-এ ধাপে ধাপে {#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"`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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` থামে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`"ADOBECODEBANC", "ABC"`-এ window বড় হয়ে সব ঢাকা পড়ার পর বাঁ দিক টেনে শেষমেশ সবচেয়ে ছোট বৈধ window `"BANC"` মেলে। `"a","a"`-তে এক অক্ষরেই ঢাকা → `"a"`। `"a","aa"`-তে কখনো দুটো a জোগাড় হয় না → `have` কখনো `required` ছোঁয় না → `""`। `"ab","b"`-তে `"b"`। খালি `s`-এ শুরুতেই `""`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 টেনে ফেলা — আগে দৈর্ঘ্য তুলনা করে রাখো, পরে অক্ষর বের করো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#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/](../../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/README.md))। এই note দেখায় দুটো chapter-এর idea মিশে কীভাবে একটা hard string problem সারে। সম্পূর্ণ আলোচনা [../patterns.md](../patterns.md)-র Pattern 1-এ (window সংস্করণসহ)।
### পরের অনুশীলন {#22-similar-harder-problems}
- Substring with Concatenation of All Words —