Problem link ও উৎস
- **Original source:** Classic cross-topic capstone interview problem (sliding window family)
- **Platform:** LeetCode —
- **Topic:** strings + hashing
- **Difficulty:** Medium
- **Pattern:** Sliding window + hashmap (variable-size window)
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **02 strings** (string-এর উপর একটা চলমান window, character-এর index নিয়ে কাজ) আর **05 hashing** (প্রতিটা character শেষ কোথায় দেখেছি তা hashmap-এ রাখা)। দুই tool জোড়া লাগলেই O(n) sliding window।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা string দেওয়া আছে। তোমার কাজ: এমন একটা **পরপর থাকা (contiguous) substring** খুঁজে বের করো, যার ভেতরে কোনো character দু'বার আসেনি — সব আলাদা। আর সেই rule মানা substring-গুলোর মধ্যে সবচেয়ে **লম্বাটার দৈর্ঘ্য** return করো (substring-টা না, শুধু length)।
```text
string : "abcabcbb"
সেরা substring : "abc" -> length = 3
```
### Input ও output {#8-example-input-and-output}
```text
Input : "abcabcbb" -> Output: 3 # "abc"
Input : "bbbbb" -> Output: 1 # "b"
Input : "pwwkew" -> Output: 3 # "wke" (মনে রেখো "pwke" subsequence, substring না)
Edge case 1 (খালি string): Input: "" -> Output: 0
Edge case 2 (সব আলাদা): Input: "au" -> Output: 2
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা সরু গলির ভেতর দিয়ে হাঁটছ আর পথে যাকেই দেখছ তার নাম একটা খাতায় লিখছ। নিয়ম: গলিতে একই লোক দু'বার থাকতে পারবে না। নতুন কারো সাথে দেখা হলে, যদি সে আগে থেকেই গলিতে থাকে, তুমি পেছন থেকে ততজন বের করে দাও যতক্ষণ না সেই পুরনো জনটা বাইরে চলে যায়। সারা পথে গলিতে একসাথে সবচেয়ে বেশি যত লোক ছিল — সেটাই উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **02 strings** থেকে: string-এর উপর বাঁ-থেকে-ডান একটা **window** (`left`, `right` দুটো pointer), আর কোন character কোথায় বসে আছে সেই thinking।
- **05 hashing** থেকে: প্রতিটা character শেষবার কোন index-এ দেখেছি তা একটা **hashmap**-এ রাখা — যাতে duplicate পেলে O(1)-এ জানা যায় কোথা থেকে window সরাতে হবে।
একা window scan তোমাকে দেয় টুকরো বড়/ছোট করার ক্ষমতা; একা hashmap দেয় "এটা কি আগে দেখেছি, কোথায়" জানার ক্ষমতা। দুটো মিললে O(n)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **monotone window invariant**: window `[left, right]`-এর ভেতরে সবসময় সব character আলাদা — এই শর্ত আমরা ভাঙতে দিই না। নতুন character `s[right]` যোগ করার সময় যদি সে আগে এই window-এর ভেতরেই দেখা থাকে (`last[ch] >= left`), তাহলে `left`-কে ঠিক তার পরের ঘরে লাফ দিয়ে নিয়ে যাই: `left = last[ch] + 1`। এতে duplicate-টা window-র বাইরে পড়ে যায়, invariant আবার ঠিক। প্রতি step-এ window-র দৈর্ঘ্য `right - left + 1`, তার সর্বোচ্চটাই উত্তর।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো জিনিস লাগে — **দুটো integer pointer** (`left`, `right`) window-র সীমানা ধরতে, আর একটা **hashmap** (`last`: character → শেষ দেখা index)। pointer দুটো 02 strings-এর window thinking থেকে, hashmap 05 hashing থেকে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
আমরা প্রতি step-এ জানতে চাই: "এই character কি window-র ভেতরে আগে আছে, আর থাকলে ঠিক কোথায়?" — এটা একটা **lookup-by-key** প্রশ্ন, hashmap-এর জন্মগত কাজ (05 hashing), O(1)-এ উত্তর। আর window-টা contiguous বলে শুধু দুই প্রান্ত (`left`, `right`) মনে রাখলেই চলে, পুরো substring store করতে হয় না (02 strings-এর pointer thinking)। তাই hashmap + দুটো pointer-ই নিখুঁত ফিট।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য substring (`i` থেকে `j`) ধরো, চেক করো তার সব character আলাদা কিনা, আলাদা হলে length মনে রাখো।
```text
for i in range(n):
for j in range(i, n):
if all chars in s[i..j] are distinct:
best = max(best, j - i + 1)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop (`i`, `j`) সব substring ধরে — O(n^2)-টা, আর প্রতিটার "সব আলাদা?" check আবার O(n) (একটা set ভরে দেখা)। মোট **O(n^3)** (set caching করলে O(n^2))। মূল অপচয়: একটা character window-র ভেতরে আছে কিনা তা বারবার নতুন করে যাচাই করা — অথচ সেটা hashmap (05) মনে রাখলে O(1)-এ জানা যেত।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **যখন একটা duplicate character পাও, পুরো window নতুন করে শুরু করার দরকার নেই** — শুধু `left`-কে আগের duplicate-এর ঠিক পরের ঘরে লাফ দেওয়াও যথেষ্ট। মাঝখানের সব character এখনো valid, তাদের ফেলে দিলে কাজ নষ্ট হয়। এই "left কে jump করানো" চিন্তাই O(n^3) থেকে O(n)-এ নামায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
বাঁ থেকে ডান `right` একবার হাঁটাও। প্রতিটা নতুন character-এর শেষ-দেখা index `last`-এ রাখো। `s[right]` যদি বর্তমান window-র ভেতরেই আগে দেখা থাকে (`last[ch] >= left`), `left`-কে `last[ch] + 1`-এ সরাও — এতে duplicate বাদ। প্রতি step-এ window length `right - left + 1` হিসাব করে `best`-এ সবচেয়ে বড়টা জমাও। `right` একবারই পুরো string পার করে — তাই O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা substring আলাদা করে পরীক্ষা করব" ভাবার বদলে ভাবো "একটাই window রাখব, যার ভেতরে কখনো duplicate ঢুকতে দেব না।" duplicate দেখলেই বাঁ প্রান্তটা ঠিক ততটুকু সরিয়ে দাও যতটুকু লাগে — পুরো O(n^2) search একটা single-pass window-এ গলে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`"abcabcbb"` দিয়ে window-র (`[left..right]`) নড়াচড়া দেখি:
```text
right=0 'a': window "a" last={a:0} len=1 best=1
right=1 'b': window "ab" last={a:0,b:1} len=2 best=2
right=2 'c': window "abc" last={a:0,b:1,c:2} len=3 best=3
right=3 'a': 'a' আগে index 0 (>=left) -> left=1
window "bca" last={a:3,b:1,c:2} len=3 best=3
right=4 'b': 'b' আগে index 1 (>=left) -> left=2
window "cab" last={a:3,b:4,c:2} len=3 best=3
right=5 'c': 'c' আগে index 2 (>=left) -> left=3
window "abc" last={a:3,b:4,c:5} len=3 best=3
right=6 'b': 'b' আগে index 4 (>=left) -> left=5
window "cb" last={a:3,b:6,c:5} len=2 best=3
right=7 'b': 'b' আগে index 6 (>=left) -> left=7
window "b" last={a:3,b:7,c:5} len=1 best=3
উত্তর: 3
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `"pwwkew"`:
1. শুরু: `left = 0`, `best = 0`, `last = {}`
2. `right=0 'p'`: window `"p"`, `last={p:0}`, len 1, `best=1`
3. `right=1 'w'`: window `"pw"`, `last={p:0,w:1}`, len 2, `best=2`
4. `right=2 'w'`: `'w'` আগে index 1 (`>= left=0`) → `left=2`; window `"w"`, `last={p:0,w:2}`, len 1, `best=2`
5. `right=3 'k'`: window `"wk"`, `last={...,k:3}`, len 2, `best=2`
6. `right=4 'e'`: window `"wke"`, `last={...,e:4}`, len 3, `best=3`
7. `right=5 'w'`: `'w'` আগে index 2 (`>= left=2`) → `left=3`; window `"kew"`, len 3, `best=3`
8. Loop শেষ → return `best = 3`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def length_of_longest_substring(s):
last = {} # character -> শেষ দেখা index
left = 0 # window-র বাঁ প্রান্ত
best = 0 # সবচেয়ে বড় valid window length
for right, ch in enumerate(s):
# ch যদি বর্তমান window-র ভেতরেই আগে থাকে, left-কে লাফ দেওয়াও
if ch in last and last[ch] >= left:
left = last[ch] + 1
last[ch] = right # ch-এর শেষ দেখা index আপডেট
best = max(best, right - left + 1) # পথের সেরা length
return best
# ---- tests ----
assert length_of_longest_substring("abcabcbb") == 3
assert length_of_longest_substring("bbbbb") == 1 # সব একই
assert length_of_longest_substring("pwwkew") == 3
assert length_of_longest_substring("") == 0 # খালি string
assert length_of_longest_substring("au") == 2 # সব আলাদা
assert length_of_longest_substring("dvdf") == 3 # left jump test
assert length_of_longest_substring("tmmzuxt") == 5 # "mzuxt"
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `last = {}` — character → শেষ index রাখার hashmap (05 hashing)।
- `left = 0` — window-র বাঁ প্রান্ত; এখান থেকে `right` পর্যন্ত সব আলাদা।
- `best = 0` — খালি string হলেও সঠিক 0 দেয়।
- `for right, ch in enumerate(s)` — ডান প্রান্ত একবার scan (02 strings-এর single pass)।
- `if ch in last and last[ch] >= left` — duplicate কি **বর্তমান window-র ভেতরে**? পুরনো (window-র বাইরের) দেখা গোনায় ধরা যাবে না, তাই `>= left` শর্তটা জরুরি।
- `left = last[ch] + 1` — বাঁ প্রান্তকে duplicate-এর ঠিক পরে লাফ দাও।
- `last[ch] = right` — এই character-এর শেষ index আপডেট।
- `best = max(best, right - left + 1)` — বর্তমান window length, সেরাটা জমাও।
- `return best` — পুরো string দেখার পর সবচেয়ে লম্বা valid window।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`"abcabcbb"`-এ প্রথম তিন step-এ window `"abc"` হয়ে `best=3`। এরপর প্রতিটা পুনরাবৃত্ত character `left`-কে সামনে ঠেলে দেয়, কিন্তু window আর 3-র বেশি বড় হতে পারে না, তাই return 3 — assert pass। `"bbbbb"`-এ প্রতিবার `left` লাফায়, window সবসময় 1, return 1। খালি string-এ loop চলেই না, return 0। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — `right` পুরো string-এ ঠিক একবার এগোয়, `left`-ও কখনো পিছোয় না (মোট মিলে n বার সামনে যায়), প্রতি step-এ hashmap কাজ O(1)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(min(n, k))** — hashmap-এ একসাথে যত আলাদা character থাকতে পারে (`k` = alphabet size, বা string ছোট হলে n)। শুধু character set-এর সমান, পুরো substring store করতে হয় না (02 strings + 05 hashing-এর মিতব্যয়িতা)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `if ch in last` লিখে `>= left` শর্তটা ভুলে যাওয়া — তখন window-র **বাইরের** পুরনো দেখা-ও `left`-কে পেছনে টেনে নেয়, window ভুল ছোট হয় (যেমন `"abba"`)।
- substring আর subsequence গুলিয়ে ফেলা — এখানে character পরপর থাকতে হবে, এদিক-ওদিক থেকে তুলে নেওয়া যাবে না।
- length হিসাবে `right - left` লেখা — সঠিক `right - left + 1` (দুই প্রান্তই inclusive)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: string-এর উপর variable-size window চালানো (02 strings-এর [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md), window family) + character → index রাখার hashmap (05 hashing-এর [../../05-hashing/](../../05-hashing/README.md))। এই দুটো cold অবস্থায় জানা থাকলে এই sliding window নিজে থেকেই দাঁড়িয়ে যায়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Longest Substring with At Most K Distinct Characters (window invariant একটু আলাদা — at most k key) —