Problem link ও উৎস
- **Original source:** Classic seen-set-of-windows / rolling-hash teaser exercise
- **Platform:** LeetCode —
- **Topic:** hash set (sliding-window keys)
- **Difficulty:** Medium
- **Pattern:** seen-set of windows / rolling-hash teaser
- **Basic idea inherited from:** seen-set + substring keys — প্রতিটা window-কে একটা key বানিয়ে "আগে দেখেছি?" জিজ্ঞেস করা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা DNA string `s` দেওয়া আছে, যেটায় শুধু চারটা অক্ষর — `'A'`, `'C'`, `'G'`, `'T'`। যেসব **10-অক্ষরের পরপর টুকরো (substring)** string-টায় **একাধিকবার** আসে, সেগুলোর তালিকা ফেরত দিতে হবে (প্রতিটা একবার করে)।
```text
s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGGG"
"AAAAACCCCC" দুবার আসে, "CCCCCAAAAA" দুবার আসে
উত্তর: ["AAAAACCCCC", "CCCCCAAAAA"]
```
### Input ও output {#8-example-input-and-output}
```text
Input : "AAAAACCCCCAAAAACCCCCCAAAAAGGGGG" Output: ["AAAAACCCCC", "CCCCCAAAAA"]
Input : "AAAAAAAAAAAAA" (13টা A) Output: ["AAAAAAAAAA"]
Input : "AAAAAAAAA" (দৈর্ঘ্য 9) Output: [] (10-window-ই হয় না)
Input : "ACGTACGTAC" (দৈর্ঘ্য ঠিক 10) Output: [] (একটাই window, পুনরাবৃত্তি নেই)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা লম্বা গানের প্রতিটা ১০-সেকেন্ডের টুকরো শুনছ আর ভাবছ "এই সুরটা কি আগে শুনেছি?"। তুমি প্রতিবার পুরো গান আবার শোনো না — মাথায় শোনা টুকরোগুলোর একটা সেট রাখো; নতুন টুকরো এলেই সেই সেটে মিলিয়ে দেখো। যেটা দ্বিতীয়বার বাজল, সেটাকে "পুনরাবৃত্ত" তালিকায় তোলো — কিন্তু একবারই, যতবারই বাজুক।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **seen-set** (Pattern 4)-এর সরাসরি সম্প্রসারণ — "এটা কি আগে দেখেছি?" O(1)-এ। নতুনত্ব হলো: এখন element একটা একক সংখ্যা নয়, একটা গোটা 10-অক্ষরের **window**। প্রতিটা window-কে একটা key (substring নিজেই, বা তার hash) ভেবে set-এ ফেলি। এখান থেকেই **rolling hash** (Pattern 7)-এর দরজা খোলে: window-কে সংখ্যা বানিয়ে slide করলে key update হয় O(1)-এ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: একটা দৈর্ঘ্য-`n` string-এ ঠিক `n - 10 + 1`টা 10-অক্ষরের window আছে — একটা একটা করে এক ঘর ডানে সরে। duplicate ধরা মানে "এই window-টা কি আগের কোনো position-এ হুবহু এসেছিল?" — অর্থাৎ window-কে একটা identity (key) দিয়ে seen-set-এ খোঁজা। rolling hash-এর গণিতটা হলো positional/place-value: string-কে কোনো base-এর সংখ্যা ধরে, window slide করলে বেরিয়ে-যাওয়া অক্ষরের contribution বিয়োগ, বাকিটা multiply, ঢোকা অক্ষর যোগ — সবই modular arithmetic ([../../01-math-based-programming-fundamentals/02-modular-arithmetic/](../../01-math-based-programming-fundamentals/02-modular-arithmetic/README.md))।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো **hash set**: একটা `seen` (এ পর্যন্ত দেখা সব window-key), আর একটা `repeated` (যেগুলো অন্তত দুবার এসেছে — যাতে উত্তরে ডুপ্লিকেট না ঢোকে)। set কারণ আমাদের শুধু "আছে কি নেই" আর "অনন্য কি না" দরকার, count নয়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতিটা window-এ আমরা জিজ্ঞেস করি "এই key কি `seen`-এ আছে?" — set গড়ে **O(1)**। থাকলে `repeated`-এ যোগ (set হওয়ায় একই window বহুবার এলেও উত্তরে একবারই)। list হলে প্রতিবার membership-check O(n) হতো, পুরোটা O(n^2)। set সেই খোঁজাকে instant করে আর অনন্যতা ফ্রি-তে রাখে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা 10-window নাও, তারপর তার ডানের প্রতিটা 10-window-র সাথে মিলিয়ে দেখো একই কি না।
```text
প্রতিটা শুরু i-র জন্য:
win = s[i : i+10]
প্রতিটা j > i-র জন্য:
s[j : j+10] == win হলে win-কে উত্তরে রাখো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop, প্রতিটায় আবার 10-অক্ষর তুলনা — মোটামুটি **O(n^2 · 10)**। অপচয়টা seen-set-এর মতোই: প্রতিটা window-র জন্য আমরা সামনের পুরো string আবার scan করছি, যদিও "আগে দেখেছি কি না" প্রশ্নটা একটা set একবারেই বলে দিতে পারে। সামনে খোঁজা বন্ধ করে পেছনের স্মৃতিতে তাকালেই O(n)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **"পরে repeat করবে?" প্রশ্নটা উল্টে "আগে এসেছিল?"-তে আনা যায়** — আর সেটা seen-set গড়ে O(1)-এ বলে। প্রতিটা window-কে একটা key ভাবো; key আগে set-এ থাকলেই duplicate। উত্তরের অনন্যতা ধরতে দ্বিতীয় একটা set যথেষ্ট।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
string-এর উপর একবার হাঁটো, প্রতিটা শুরু `i`-তে `window = s[i:i+10]` নাও। `window` যদি `seen`-এ থাকে → `repeated`-এ যোগ করো; নইলে `seen`-এ যোগ করো। শেষে `repeated`-এর সব element ফেরত দাও। এক pass, প্রতিটা window key O(1) (rolling hash হলে slice-ও O(1))। মোট কার্যত O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** *একটা window-কে একটা একক "জিনিস" (key) ভাবো, তারপর seen-set-এর "আগে দেখেছি?" সরাসরি লাগাও।* এক ধাপ এগিয়ে — সেই key-কে slice না বানিয়ে একটা rolling সংখ্যা বানালে প্রতিটা slide O(1)। এই "window → key → set" চিন্তাই string matching, anagram-window, repeated-substring সব জায়গায় ফিরে আসে।
### ছবিতে বোঝা {#7-visual-explanation}
ছোট করে দৈর্ঘ্য-3 window দিয়ে ধারণাটা (আসল problem-এ 10): `s = "AAAAA"`। window এক ঘর করে সরে, `seen`-এ মেলে কি না দেখি:
```text
i=0 win="AAA" AAA in {}? না → seen={AAA}
i=1 win="AAA" AAA in seen? হ্যাঁ → repeated={AAA}
i=2 win="AAA" AAA in seen? হ্যাঁ → repeated={AAA} (set, তাই একবারই)
উত্তর: ["AAA"]
```
প্রতিবার শুধু এক ঘর ডানে সরছি; rolling hash থাকলে এই slide-এ key-ও O(1)-এ আপডেট হতো।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `s = "AAAAAAAAAAAAA"` (13টা A), window দৈর্ঘ্য 10:
1. শুরু: `seen = {}`, `repeated = {}`। window সংখ্যা `13 - 10 + 1 = 4`।
2. `i=0`: `win = "AAAAAAAAAA"`; `seen`-এ নেই → `seen = {"AAAAAAAAAA"}`।
3. `i=1`: একই `win`; `seen`-এ আছে → `repeated = {"AAAAAAAAAA"}`।
4. `i=2, i=3`: আবার একই `win`; ইতিমধ্যে `repeated`-এ আছে, set হওয়ায় বদল নেই।
5. উত্তর: `["AAAAAAAAAA"]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def find_repeated_dna(s):
seen = set() # এ পর্যন্ত দেখা সব 10-window
repeated = set() # যেগুলো অন্তত দুবার এসেছে
for i in range(len(s) - 9): # শেষ শুরু-index = len(s) - 10
window = s[i:i + 10]
if window in seen: # আগে দেখেছি? → পুনরাবৃত্ত
repeated.add(window)
else:
seen.add(window)
return sorted(repeated) # স্থির ক্রমে ফেরত (test-এর সুবিধায়)
# ---- tests ----
assert find_repeated_dna("AAAAACCCCCAAAAACCCCCCAAAAAGGGGG") == ["AAAAACCCCC", "CCCCCAAAAA"]
assert find_repeated_dna("AAAAAAAAAAAAA") == ["AAAAAAAAAA"] # 13টা A
assert find_repeated_dna("AAAAAAAAA") == [] # দৈর্ঘ্য 9, window-ই হয় না
assert find_repeated_dna("ACGTACGTAC") == [] # ঠিক 10, একটাই window
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `seen = set()` — এ পর্যন্ত দেখা প্রতিটা 10-অক্ষর window জমে।
- `repeated = set()` — যেগুলো দ্বিতীয়বার দেখা গেছে; set হওয়ায় উত্তরে কখনো ডুপ্লিকেট নয়।
- `for i in range(len(s) - 9)` — শুরু-index 0 থেকে `len(s) - 10` পর্যন্ত; `range(len(s) - 9)` ঠিক ততগুলো দেয়।
- `window = s[i:i + 10]` — এখনকার 10-অক্ষর টুকরো; এটাই আমাদের key।
- `if window in seen` — set membership গড়ে O(1); আগে থাকলে এটি পুনরাবৃত্ত।
- `repeated.add(window)` / `seen.add(window)` — হয় পুনরাবৃত্ত তালিকায়, নয়তো প্রথমবার দেখা হিসেবে নথিভুক্ত।
- `return sorted(repeated)` — set-এর ক্রম অনিশ্চিত, তাই sort করে স্থির উত্তর (assert মেলানো সহজ)।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথম case-এ `"AAAAACCCCC"` ও `"CCCCCAAAAA"` দুটোই দ্বিতীয়বার দেখা যায় → sort করে `["AAAAACCCCC", "CCCCCAAAAA"]`। 13টা A-তে একই 10-window চারবার আসে, কিন্তু set হওয়ায় উত্তর `["AAAAAAAAAA"]`। দৈর্ঘ্য 9-এ loop চলেই না → `[]`। ঠিক 10 দৈর্ঘ্যে একটাই window, পুনরাবৃত্তি নেই → `[]`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** কার্যত — `n` window, প্রতিটায় slice + set operation। Python slice 10-অক্ষর কপি করে (ধ্রুবক 10), তাই গড়ে O(n)। rolling hash দিয়ে slice-ও O(1) করা যায়, constant ছোট হয়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — worst case-এ প্রায় সব আলাদা window দুই set-এ জমতে পারে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- window-সীমা ভুল করা — শেষ বৈধ শুরু-index `len(s) - 10`; `range(len(s) - 9)` ঠিক, `range(len(s) - 10)` শেষ window বাদ দেয়, `range(len(s))` সীমা ছাড়ায়।
- উত্তরে ডুপ্লিকেট আসা — একই window তিনবার এলে list-এ তিনবার ঢুকে যেতে পারে; `repeated` কে **set** রাখলে সমস্যা নেই।
- দৈর্ঘ্য < 10 case ভুলে যাওয়া — তখন কোনো window-ই হয় না; loop ফাঁকা চললে স্বাভাবিকভাবেই `[]` ফেরে, কিন্তু সীমা ভুল হলে index error হতে পারে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: seen-set (Pattern 4, Contains Duplicate #2-এর আত্মীয়) — শুধু element এখন একটা গোটা substring window। এই note rolling hash (Pattern 7)-এর প্রবেশদ্বার: window-কে key ভাবা, আর সেই key-কে slide-এ O(1) আপডেট করার ধারণা। rolling hash-এর গণিত আসে [../../01-math-based-programming-fundamentals/02-modular-arithmetic/](../../01-math-based-programming-fundamentals/02-modular-arithmetic/README.md) থেকে। সম্পূর্ণ আলোচনা [../patterns.md](../patterns.md)-র Pattern 4 ও 7-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Longest Duplicate Substring —