Problem link ও উৎস
- **Original source:** Classic sliding-window exercise
- **Platform:** LeetCode —
- **Topic:** string / sliding window
- **Difficulty:** Medium
- **Pattern:** sliding window (variable size, repair করে চলা)
- **Basic idea inherited from:** two pointers + frequency counting — একই দিকে চলা দুই pointer, আর কোন char কোথায় দেখেছি তা মনে রাখা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা string `s` দেওয়া। এর মধ্যে এমন সবচেয়ে লম্বা **substring** (পরপর থাকা অংশ) খুঁজে বের করো যেখানে কোনো character দুবার নেই। তোমাকে সেই সবচেয়ে লম্বা substring-এর **দৈর্ঘ্য** ফেরত দিতে হবে।
```text
s = "abcabcbb"
repeat ছাড়া সবচেয়ে লম্বা: "abc" -> দৈর্ঘ্য 3
```
### Input ও output {#8-example-input-and-output}
```text
Input : "abcabcbb" -> 3 ("abc")
Input : "bbbbb" -> 1 ("b")
Input : "pwwkew" -> 3 ("wke")
Edge case 1 (খালি): "" -> 0
Edge case 2 (সব আলাদা): "au" -> 2 ("au")
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি রাস্তায় একটানা দোকান গুনছ, শর্ত — একই নামের দোকান window-তে দুবার থাকতে পারবে না। নতুন দোকান valid হলে window বড় করো। যদি এমন নামের দোকান আসে যেটা আগেই window-তে আছে, তখন বাঁ প্রান্তটা সেই পুরনো দোকানের ঠিক পরে এনে ফেলো — তাহলে আবার সব নাম আলাদা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **two pointers** আর **frequency counting** দুটোকেই মেলায়: একটা window `[start..i]` রাখি যেটা সবসময় unique রাখার চেষ্টা করে। `i` (ডান প্রান্ত) এগোতে থাকে, আর কোন character শেষ কোথায় দেখেছি সেটা মনে রাখি — duplicate এলে বাঁ প্রান্ত `start` লাফ দিয়ে সরে repair করি। 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: একটা window valid (সব unique) হলে, ডান প্রান্ত এক ঘর বাড়ানোর পর যদি duplicate তৈরি হয়, তবে সেই repeated character-এর **আগের অবস্থানের ঠিক পরে** পর্যন্ত বাঁ প্রান্ত টেনে আনলেই window আবার valid — মাঝের কোনো অংশ scratch থেকে গোনার দরকার নেই। তাই প্রতিটা index একবার ঢোকে, একবার বের হয় → O(n)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **hash map (dict)** `last`, যেখানে key = character, value = সেই character সর্বশেষ যে index-এ দেখা গেছে। সাথে দুটো integer — `start` (window-এর বাঁ প্রান্ত) আর `best` (এ যাবৎ সেরা দৈর্ঘ্য)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Dict-এর lookup average **O(1)**, তাই "এই character কি window-এর ভিতরে আগে দেখেছি, আর কোথায়?" — দুটোই সাথে সাথে জানা যায়। character-এর শেষ index জানা থাকলে বাঁ প্রান্তকে এক লাফেই সঠিক জায়গায় নেওয়া যায়, একটা একটা করে সরাতে হয় না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা শুরু-index থেকে যত দূর পর্যন্ত সব character unique থাকে দেখো, প্রতিবার একটা set-এ ভরে check করে।
```text
best = 0
for i in range(n):
seen = set()
for j in range(i, n):
if s[j] in seen: break
seen.add(s[j])
best = max(best, j - i + 1)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা শুরু-point থেকে আবার সামনে স্ক্যান করা মানে **O(n^2)** (worst case)। বারবার একই অংশ পুনরায় গোনা হচ্ছে — অথচ window valid রাখলে আগের কাজটুকু ফেলে দেওয়ার দরকার নেই, শুধু বাঁ প্রান্ত সরিয়ে repair করলেই হয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: window ভাঙলে (duplicate এলে) পুরো window scratch থেকে শুরু করতে হয় না। repeated character-এর আগের অবস্থানের পরপরই বাঁ প্রান্ত নিয়ে গেলে valid window ফিরে আসে, আর তার ভেতরের কাজ এখনো ঠিক আছে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
ডান প্রান্ত `i` এক এক করে এগোও। প্রতিটা character `ch`-এ দেখো সে আগে কোথায় দেখা গেছে (`last[ch]`)। যদি সেই অবস্থান এখনকার window-এর ভিতরে (`>= start`) হয়, তবে `start = last[ch] + 1` করে window-কে repeat-মুক্ত করো। তারপর `last[ch] = i` update করে `best`-কে `i - start + 1` দিয়ে বড় করার চেষ্টা করো। এক pass, O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা শুরু থেকে কত দূর যেতে পারি" (O(n^2)) ভুলে গিয়ে ভাবো "একটা valid window রাখব, ভাঙলে শুধু বাঁ প্রান্ত সরিয়ে সারিয়ে নেব।" restart নয়, repair — এটাই sliding window-এর প্রাণ।
### ছবিতে বোঝা {#7-visual-explanation}
`s = "abcabcbb"` দিয়ে window-এর চলাফেরা:
```text
[a]bcabcbb window "a" best 1
[ab]cabcbb window "ab" best 2
[abc]abcbb window "abc" best 3
a[bca]bcbb 'a' আগে index 0-এ -> start = 0+1, window "bca" best 3
ab[cab]cbb 'b' আগে index 1-এ -> start = 1+1, window "cab" best 3
abc[abc]bb c আগে index 2-এ -> start=3, window abc, best 3
abcab[cb]b b আগে index 4-এ -> start=5, window cb, best 3
abcabcb[b] b আগে index 6-এ -> start=7, window b, best 3
answer: 3
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `"abcabcbb"`:
1. `start=0`, `best=0`, `last={}`। `i=0 'a'`: নতুন → `last={a:0}`, `best=1`।
2. `i=1 'b'`: নতুন → `last={a:0,b:1}`, `best=2`।
3. `i=2 'c'`: নতুন → `last={a:0,b:1,c:2}`, `best=3`।
4. `i=3 'a'`: `last[a]=0 >= start 0` → `start=1`; `last[a]=3`; দৈর্ঘ্য `3-1+1=3`, `best=3`।
5. `i=4 'b'`: `last[b]=1 >= start 1` → `start=2`; `last[b]=4`; দৈর্ঘ্য 3।
6. বাকিগুলোতেও `best` 3-ই থাকে। ফল: `3`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def length_of_longest_substring(s):
last = {} # char -> শেষ যে index-এ দেখা গেছে
start = 0 # window-এর বাঁ প্রান্ত
best = 0
for i, ch in enumerate(s):
if ch in last and last[ch] >= start:
start = last[ch] + 1 # duplicate-এর পরে window টানো
last[ch] = i # এই char-এর শেষ index update
best = max(best, i - start + 1)
return best
# ---- tests ----
assert length_of_longest_substring("abcabcbb") == 3 # "abc"
assert length_of_longest_substring("bbbbb") == 1 # "b"
assert length_of_longest_substring("pwwkew") == 3 # "wke"
assert length_of_longest_substring("") == 0 # খালি
assert length_of_longest_substring("au") == 2 # "au"
assert length_of_longest_substring("dvdf") == 3 # "vdf"
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `last = {}` — প্রতিটা character শেষ কোথায় দেখেছি তার map।
- `start = 0` — বর্তমান unique window-এর বাঁ প্রান্ত।
- `for i, ch in enumerate(s)` — ডান প্রান্ত `i` আর তার character একসাথে।
- `if ch in last and last[ch] >= start` — character আগে দেখেছি **এবং** সেটা এখনকার window-এর ভিতরে কিনা; এই দুটো শর্তই জরুরি, নয়তো পুরনো (window-এর বাইরের) দেখা ভুল করে start সরাবে।
- `start = last[ch] + 1` — duplicate-এর ঠিক পরে বাঁ প্রান্ত নিয়ে গিয়ে repair।
- `last[ch] = i` — এই character-এর সর্বশেষ অবস্থান update।
- `best = max(best, i - start + 1)` — বর্তমান window-এর দৈর্ঘ্য দিয়ে সেরা update।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`"abcabcbb"` → "abc" পর্যন্ত best 3, পরে duplicate এলে window slide করে, best 3-ই থাকে → `3`, assert pass। `"bbbbb"` → প্রতিবার start লাফায়, window 1 → `1`; `"pwwkew"` → "wke" দেয় `3`; `""` → loop চলেই না, `0`; `"au"` → `2`; `"dvdf"` → "vdf" দেয় `3`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
`Map` দিয়ে last-seen index — duplicate এলে বাঁ প্রান্ত repair করে চলা।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// length of longest substring without repeating chars (sliding window)
function lengthOfLongestSubstring(s) {
const last = new Map(); // char -> শেষ যে index-এ দেখা গেছে
let start = 0, best = 0;
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if (last.has(ch) && last.get(ch) >= start) {
start = last.get(ch) + 1; // duplicate-এর পরে window টানো
}
last.set(ch, i); // এই char-এর শেষ index update
best = Math.max(best, i - start + 1);
}
return best;
}
// ---- test cases (example + edge) ----
assert(lengthOfLongestSubstring("abcabcbb") === 3, "abc");
assert(lengthOfLongestSubstring("bbbbb") === 1, "single-repeat");
assert(lengthOfLongestSubstring("pwwkew") === 3, "wke");
assert(lengthOfLongestSubstring("") === 0, "empty"); // edge
assert(lengthOfLongestSubstring("au") === 2, "all-unique");
assert(lengthOfLongestSubstring("dvdf") === 3, "vdf"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** `last.get(ch) >= start` শর্তটা জরুরি — শুধু `last.has(ch)` দেখলে window-এর বাইরের পুরনো দেখা ভুল করে `start` পিছিয়ে দেবে। window দৈর্ঘ্য `i - start + 1` (দুই প্রান্ত inclusive)।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function lengthOfLongestSubstring(s: string): number {
const last = new Map