Problem link ও উৎস
- **Original source:** Classic shrinkable sliding-window exercise
- **Platform:** LeetCode —
- **Topic:** string / sliding window
- **Difficulty:** Hard
- **Pattern:** sliding window (shrinkable) + frequency counting
- **Basic idea inherited from:** Longest-unique window (problem 10) + character counts — expand করে valid বানাও, তারপর shrink করে minimal
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো string `s` আর `t` দেওয়া। `s`-এর এমন সবচেয়ে **ছোট** substring (window) খুঁজে বের করো যেটার ভেতরে `t`-এর প্রতিটা character অন্তত যতবার `t`-তে আছে, ততবার আছে (multiplicity সহ)। এমন window না থাকলে খালি string ফেরত দাও।
```text
s = "ADOBECODEBANC", t = "ABC"
A, B, C তিনটাই ধরে এমন সবচেয়ে ছোট window: "BANC"
```
### Input ও output {#8-example-input-and-output}
```text
Input : s = "ADOBECODEBANC", t = "ABC" -> "BANC"
Input : s = "a", t = "a" -> "a"
Edge case 1 (যথেষ্ট char নেই): s = "a", t = "aa" -> ""
Edge case 2 (s খালি/অমিল): s = "", t = "a" -> ""
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা shopping list (`t`) আছে — 1টা আপেল, 1টা কলা, 1টা চেরি। তুমি একটা লম্বা তাকের (`s`) সামনে দিয়ে হাঁটছ, ডান হাতে জিনিস তুলছ যতক্ষণ না list-এর সব আইটেম জোগাড় হয়। জোগাড় হওয়ার সাথে সাথে বাঁ দিক থেকে অপ্রয়োজনীয় জিনিস ফেলে দিতে থাকো — কোনো দরকারি আইটেম কমে গেলে থামো। সবচেয়ে আঁটোসাঁটো ঝুড়িটাই উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত হলো **sliding window** (problem 10, Longest Substring Without Repeating)। সেখানে ছিল "longest valid window"; এখানে চাই "shortest valid window" — তাই দিক উল্টো: ডান প্রান্ত `right` দিয়ে window **বড় করে valid বানাই**, valid হওয়ার সাথে সাথে বাঁ প্রান্ত `left` দিয়ে **যতটা সম্ভব ছোট করি**। সাথে problem 3-এর **character count** লাগে — কোন অক্ষর কতবার দরকার তা মেলাতে। sliding-window-এর math: [../../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/](../../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/README.md)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুটো invariant: (১) `right` শুধু সামনে যায়, `left`-ও শুধু সামনে যায় — তাই দুটো মিলে মোট `2n` ধাপ, O(n)। (২) একটা গণনা `formed` রাখি = `t`-এর কয়টা আলাদা অক্ষরের চাহিদা এখন **পুরোপুরি** মিটেছে। `formed == required` (t-এর আলাদা অক্ষর সংখ্যা) হলেই window valid — তখন left-কে এগিয়ে ছোট করার চেষ্টা করি, যতক্ষণ valid থাকে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো **hash map (dict)**: `need` (`t`-এর প্রতিটা অক্ষর কতবার লাগবে) আর `window` (চলতি window-এ প্রতিটা অক্ষর কতবার আছে)। সাথে কয়েকটা integer: `left`, `formed`, `required`, আর সেরা window-এর `best_len`/`best_left`।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রশ্নটা গণনা-নির্ভর: "এই অক্ষর কি চাহিদার সমান হলো?" — dict-এ count বাড়ানো/কমানো ও তুলনা সবই average **O(1)**। `formed` counter রাখায় প্রতিবার পুরো `need` map স্ক্যান করে "সব মিটেছে কিনা" দেখার দরকার পড়ে না — শুধু যে অক্ষরটা এইমাত্র ঠিক চাহিদায় পৌঁছাল, তার জন্য `formed` এক বাড়াই/কমাই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: `s`-এর প্রতিটা শুরু-index থেকে প্রতিটা শেষ-index পর্যন্ত সব substring বানাও, প্রতিটার জন্য check করো সেটা `t`-এর সব char ধরে কিনা, valid হলে সবচেয়ে ছোটটা রাখো।
```text
best = None
for i in range(n):
for j in range(i, n):
if window s[i..j] contains all of t (count check):
best = shorter(best, s[i..j])
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সব substring O(n^2)টা, প্রতিটার জন্য আবার count-check O(n) — মোট **O(n^3)** (বা সাবধানে O(n^2))। বারবার overlapping window নতুন করে গোনা হচ্ছে। sliding window সেই কাজ পুনর্ব্যবহার করে: window এক ঘর বাড়লে শুধু একটা count update হয়, পুরোটা আবার গোনা লাগে না — মোট O(n)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: একটা valid window পেলে, আরও বড় করে নতুন valid খোঁজার দরকার নেই — বরং **বাঁ দিক থেকে ছেঁটে minimal করো**, তারপর ডান প্রান্ত আবার বাড়িয়ে পরের valid খোঁজো। `formed` counter থাকায় "valid কিনা" O(1)-এ জানা যায়, পুরো map স্ক্যান লাগে না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`need = Counter(t)`, `required = len(need)` (আলাদা অক্ষরের সংখ্যা)। `right` দিয়ে window বাড়াও; কোনো অক্ষরের window-count যখন ঠিক তার need-count ছুঁলো, `formed += 1`। যখন `formed == required` (valid), ভেতরের `while`-এ `left` এগিয়ে window ছোট করো — সবচেয়ে ছোট দৈর্ঘ্য update করতে করতে — যতক্ষণ না কোনো দরকারি অক্ষর চাহিদার নিচে নামে (তখন `formed -= 1`, valid ভাঙে)। `right` শেষ পর্যন্ত। মোট O(|s| + |t|)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব substring বানিয়ে check করব" ভোলো। ভাবো "ডান হাত দিয়ে যথেষ্ট জোগাড় করি (expand-to-valid), তারপর বাঁ হাত দিয়ে যতটা পারি ছেঁটে ফেলি (shrink-to-minimal)।" দুই প্রান্তই শুধু সামনে যায়, তাই overlapping কাজ একবারও দুবার হয় না।
### ছবিতে বোঝা {#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 = "a", t = "a"`:
1. `need = {a:1}`, `required = 1`, `formed = 0`, `left = 0`, `best_len = ∞`।
2. `right=0 'a'`: `window={a:1}`; `a` need-এ আর `window[a]==need[a]` → `formed=1`।
3. `formed == required` (1==1) → valid। দৈর্ঘ্য `0-0+1=1 < ∞` → `best_len=1`, `best_left=0`। shrink: `left_ch='a'`, `window[a]=0 < need[a]` → `formed=0`, `left=1`। `while` শেষ।
4. `right` শেষ। `best_len=1` → `s[0:1] = "a"`।
## কোড ও ব্যাখ্যা {#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)
required = len(need) # t-এর আলাদা অক্ষরের সংখ্যা
window = {}
formed = 0 # কয়টা আলাদা অক্ষরের চাহিদা পুরো হয়েছে
left = 0
best_len = float("inf")
best_left = 0
for right, ch in enumerate(s):
window[ch] = window.get(ch, 0) + 1
if ch in need and window[ch] == need[ch]:
formed += 1 # এই অক্ষর ঠিক চাহিদায় পৌঁছাল
while formed == required: # window valid -> ছোট করার চেষ্টা
if right - left + 1 < best_len:
best_len = right - left + 1
best_left = left
left_ch = s[left]
window[left_ch] -= 1
if left_ch in need and window[left_ch] < need[left_ch]:
formed -= 1 # দরকারি অক্ষর কমে গেল -> valid ভাঙল
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("", "a") == "" # s খালি
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `need = Counter(t)` — প্রতিটা অক্ষর কতবার লাগবে।
- `required = len(need)` — কয়টা **আলাদা** অক্ষরের চাহিদা মেটাতে হবে।
- `window[ch] = window.get(ch,0)+1` — ডান প্রান্তের অক্ষর window-এ যোগ।
- `if ch in need and window[ch] == need[ch]: formed += 1` — ঠিক চাহিদার সমান হলেই (বেশি হলে নয়) এক ধাপ এগোলাম।
- `while formed == required:` — window এখন সব চাহিদা মেটায়; এর ভেতরে যতটা পারি ছোট করি।
- `if right-left+1 < best_len:` — এই valid window আগের সেরার চেয়ে ছোট হলে রাখি।
- `window[left_ch] -= 1; if ... < need: formed -= 1` — বাঁ প্রান্ত ছাঁটি; দরকারি অক্ষর চাহিদার নিচে নামলে valid ভাঙে, loop থামে।
- শেষ line — কোনো valid না পেলে `""`, নইলে best স্লাইস।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`"ADOBECODEBANC"/"ABC"` → expand-shrink করতে করতে সবচেয়ে ছোট valid `"BANC"` (4) → assert pass। `"a"/"a"` → `"a"`; `"a"/"aa"` → দুটো `a` দরকার, একটাই আছে, কখনো valid হয় না → `""`; `""/"a"` → guard-এ `""`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
দুই `Map` (need/window) + `formed` counter — expand-to-valid, তারপর shrink-to-minimal।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// smallest substring of s containing all chars of t (with multiplicity)
function minWindow(s, t) {
if (!s || !t) return "";
const need = new Map();
for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
const required = need.size; // t-এর আলাদা অক্ষরের সংখ্যা
const window = new Map();
let formed = 0, left = 0;
let bestLen = Infinity, bestLeft = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
window.set(ch, (window.get(ch) || 0) + 1);
if (need.has(ch) && window.get(ch) === need.get(ch)) formed++; // ঠিক চাহিদায়
while (formed === required) { // window valid -> ছোট করো
if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestLeft = left; }
const lc = s[left];
window.set(lc, window.get(lc) - 1);
if (need.has(lc) && window.get(lc) < need.get(lc)) formed--; // valid ভাঙল
left++;
}
}
return bestLen === Infinity ? "" : s.slice(bestLeft, bestLeft + bestLen);
}
// ---- test cases (example + edge) ----
assert(minWindow("ADOBECODEBANC", "ABC") === "BANC", "classic");
assert(minWindow("a", "a") === "a", "single");
assert(minWindow("a", "aa") === "", "not-enough"); // edge
assert(minWindow("", "a") === "", "empty-s"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** `window.get(ch) === need.get(ch)` (ঠিক সমান হলে `formed++`), `>=` নয় — নাহলে একই অক্ষর বহুবার গোনা হবে। substring বের করতে `s.slice(start, end)`; "এখনো পাইনি" বোঝাতে `Infinity`।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function minWindow(s: string, t: string): string {
if (!s || !t) return "";
const need = new Map