Problem link ও উৎস
- **Original source:** Classic frequency-counting + fixed-window exercise
- **Platform:** LeetCode —
- **Topic:** hash map (word counts) + fixed-size sliding window
- **Difficulty:** Hard
- **Pattern:** frequency counting + fixed windows
- **Basic idea inherited from:** Minimum Window Substring — count মেলানো, কিন্তু এখন অক্ষরের বদলে সমান-দৈর্ঘ্যের word, আর window-এর দৈর্ঘ্য স্থির
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা string `s` আর সমান-দৈর্ঘ্যের কিছু word-এর তালিকা `words` দেওয়া আছে (word পুনরাবৃত্তও থাকতে পারে)। `s`-এর মধ্যে এমন সব শুরু-index খুঁজতে হবে যেখান থেকে শুরু করে `words`-এর **প্রতিটা word ঠিক একবার**, মাঝে কোনো ফাঁক ছাড়া, যেকোনো ক্রমে পরপর বসানো যায়।
```text
s = "barfoothefoobarman", words = ["foo", "bar"]
index 0: "barfoo" = "bar" + "foo" ✓
index 9: "foobar" = "foo" + "bar" ✓
উত্তর: [0, 9]
```
### Input ও output {#8-example-input-and-output}
```text
Input : s = "barfoothefoobarman", words = ["foo","bar"] Output: [0, 9]
Input : s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] Output: []
Input : s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] Output: [6, 9, 12]
Input : s = "", words = ["a"] Output: []
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তোমার হাতে কয়েকটা নির্দিষ্ট রঙের লেগো ব্লক — 2টা লাল, 1টা নীল (এটাই `need`)। একটা লম্বা সারিতে সমান মাপের ব্লক বসানো; তুমি জানালা দিয়ে পরপর কয়েকটা ব্লক দেখছ, ঠিক ততগুলো যত হাতে আছে। জানালার ভেতরের রঙের হিসাব যদি হুবহু তোমার হাতের হিসাবের সমান হয় — পেয়ে গেছ এক জায়গা। জানালা এক-ব্লক ডানে সরাও: বাঁয়ের ব্লক বাদ, ডানে নতুন ব্লক যোগ — পুরো গোনা নতুন করে নয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **Minimum Window Substring** (#20)-এর আত্মীয়, এক ধাপ এগিয়ে। ওখানে count ছিল অক্ষরের আর window-এর দৈর্ঘ্য পরিবর্তনশীল; এখানে count হলো **word**-এর (Pattern 1, frequency counting) আর প্রতিটা valid window-এর দৈর্ঘ্য **স্থির** (`word_len × সংখ্যা`)। তাই string-কে word-একক ধাপে হাঁটি, আর fixed-length window-এ word-count মেলাই।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: সব word সমান-দৈর্ঘ্যের (`L`) হওয়ায় একটা valid block-এর মোট দৈর্ঘ্য সবসময় `L × k` (যেখানে `k = len(words)`) — fixed। আর যেহেতু block-গুলো `L`-এর গুণিতকে শুরু হয়, প্রতিটা সম্ভাব্য শুরু-position-এর "phase" হলো `0, 1, ..., L-1`-এর কোনো একটা। তাই `L`টা আলাদা সারিবদ্ধতা (offset) ধরে word-একক ধাপে sliding window চালালে প্রতিটা শুরু-position ঠিক একবার করে বিবেচিত হয় — কোনো position বাদ যায় না, পুনরাবৃত্তও হয় না।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো **hash map / Counter**: `need` (`word → কতবার লাগবে`) আর `window` (এখনকার block-এ `word → কতবার আছে`)। সাথে কয়েকটা integer: `word_len` (`L`), `num_words` (`k`), আর প্রতি offset-এ `left`/`count`। word-গুলোকে key বানানো যায় কারণ string hashable।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
word পুনরাবৃত্ত থাকতে পারে (যেমন `["word","word","good"]`), তাই set নয়, **count** চাই — Counter ঠিক তাই দেয়, আর অনুপস্থিত key-তে 0। প্রতিটা `L`-অক্ষর টুকরোকে এক ধাপে word হিসেবে slice করে `need`-এর সাথে মেলাই, count update/lookup গড়ে **O(1)**। ফলে প্রতিটা position-এ শূন্য থেকে না গুনে incremental window চালানো যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: `s`-এর প্রতিটা সম্ভাব্য শুরু-index ধরে total দৈর্ঘ্যের টুকরো কেটে নাও, সেটাকে `L`-অক্ষরে ভাগ করে word-গুলো বের করো, তারপর সেই word-গুলোর Counter `need`-এর সমান কি না দেখো।
```text
total = L * k
প্রতিটা শুরু i (0 .. len(s)-total)-র জন্য:
block = s[i : i+total]
block-কে L-অক্ষরে ভেঙে word-গুলো বের করো
সেই word-গুলোর Counter == need হলে i-কে উত্তরে রাখো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা শুরু-index-এ আমরা পুরো block আবার `L`-অক্ষরে ভেঙে নতুন Counter বানাই — **O(n · k)**, n শুরু-position আর প্রতিটায় k word। অপচয়টা Minimum Window Substring-এর মতোই: পাশাপাশি দুটো block-এর বেশির ভাগ word একই, তবু আমরা প্রতিবার শূন্য থেকে গুনছি। offset-ভিত্তিক sliding window সেই count incremental রাখে — বাঁয়ের word বাদ, ডানের যোগ।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **word সমান-দৈর্ঘ্যের বলে শুরু-position-গুলো মাত্র `L`টা phase-এ পড়ে।** প্রতিটা phase-এ string-কে word-একক ধাপে হাঁটলে একটা সাধারণ "fixed-window, count মেলাও" sliding window-এ নেমে আসে — যেখানে window slide করলে শুধু এক word বাদ, এক word যোগ।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`need = Counter(words)`, `L = word_len`, `k = num_words`। প্রতিটা `offset` (0..L-1)-এর জন্য `left = offset`, খালি `window`, `count = 0`। `right` কে `offset` থেকে `L` ধাপে বাড়াও, প্রতিবার `word = s[right:right+L]`: word `need`-এ থাকলে `window`-এ যোগ আর `count += 1`; যদি কোনো word চাহিদার বেশি হয়, বাঁ দিক থেকে word বাদ দিতে দিতে (`left += L`) ঠিক করো; `count == k` হলে `left` একটা valid শুরু-index। word `need`-এ না থাকলে window সম্পূর্ণ রিসেট করে `left = right + L`। মোট O(L · (n/L)) = O(n) word-ছোঁয়া।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** *যখন সব টুকরো সমান-দৈর্ঘ্যের, character-একক না ভেবে token-একক ভাবো — string-কে word-এর sequence ধরে fixed-window sliding চালাও, আর `L`টা phase আলাদা করে দেখো।* এটা Minimum Window Substring-এর tweak-এর উপরে আরেক স্তর: alphabet বদলে গেছে অক্ষর থেকে word-এ, আর window হয়ে গেছে fixed-length।
### ছবিতে বোঝা {#7-visual-explanation}
`s = "barfoothefoobarman"`, `words = ["foo","bar"]`; `L=3`, `k=2`, `need = {foo:1, bar:1}`। offset 0-এ word-একক ধাপে হাঁটি:
```text
right=0 "bar" need-এ আছে window{bar:1} count=1
right=3 "foo" need-এ আছে window{bar:1,foo:1} count=2 == k → index 0 ✓
right=6 "the" need-এ নেই → window রিসেট, count=0, left=9
right=9 "foo" window{foo:1} count=1
right=12 "bar" window{foo:1,bar:1} count=2 == k → index 9 ✓
right=15 "man" need-এ নেই → রিসেট
উত্তর (offset 0): [0, 9]
```
offset 1 ও 2-তে কোনো word সারিবদ্ধ হয় না, তাই নতুন index আসে না।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `s = "barfoo"`, `words = ["foo","bar"]`; `L=3`, `k=2`, `need = {foo:1, bar:1}`, offset 0:
1. `left=0`, `window={}`, `count=0`।
2. `right=0`: `word = "bar"`, need-এ আছে → `window={bar:1}`, `count=1`। `count != k`।
3. `right=3`: `word = "foo"`, need-এ আছে → `window={bar:1, foo:1}`, `count=2`। `count == k` → `left=0` valid → উত্তরে `0`।
4. offset 1, 2-তে word সারিবদ্ধ হয় না → কিছু যোগ হয় না।
5. উত্তর: `[0]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import Counter
def find_substring(s, words):
if not s or not words:
return []
word_len = len(words[0]) # L: প্রতিটা word সমান-দৈর্ঘ্য
num_words = len(words) # k
need = Counter(words) # word -> কতবার লাগবে
result = []
for offset in range(word_len): # L টা phase / সারিবদ্ধতা
left = offset
count = 0
window = Counter()
for right in range(offset, len(s) - word_len + 1, word_len):
word = s[right:right + word_len]
if word in need:
window[word] += 1
count += 1
while window[word] > need[word]: # বেশি হয়ে গেছে → বাঁ টানো
left_word = s[left:left + word_len]
window[left_word] -= 1
left += word_len
count -= 1
if count == num_words: # ঠিক সব word মিলেছে
result.append(left)
else: # অচেনা word → রিসেট
window.clear()
count = 0
left = right + word_len
return sorted(result)
# ---- tests ----
assert find_substring("barfoothefoobarman", ["foo", "bar"]) == [0, 9]
assert find_substring("wordgoodgoodgoodbestword", ["word", "good", "best", "word"]) == []
assert find_substring("barfoofoobarthefoobarman", ["bar", "foo", "the"]) == [6, 9, 12]
assert find_substring("", ["a"]) == []
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not s or not words: return []` — খালি input-এ কোনো valid index নেই।
- `word_len`, `num_words`, `need` — `L`, `k`, আর word-চাহিদার count।
- `for offset in range(word_len)` — `L`টা সারিবদ্ধতা; প্রতিটায় string-কে word-একক ধাপে দেখি।
- `for right in range(offset, len(s) - word_len + 1, word_len)` — `L` ধাপে এগিয়ে প্রতিটা word-এর শুরু।
- `if word in need: window[word]+=1; count+=1` — চেনা word হলে window-এ যোগ।
- `while window[word] > need[word]` — এই word চাহিদার বেশি হলে বাঁ দিক থেকে word বাদ দিয়ে ভারসাম্য ফেরাই।
- `if count == num_words: result.append(left)` — ঠিক `k`টা চেনা word ভরে গেলে `left` একটা valid শুরু।
- `else: window.clear(); count=0; left=right+word_len` — অচেনা word পেলে window ভেঙে তার পরের word থেকে নতুন করে শুরু।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`"barfoothefoobarman", ["foo","bar"]`-এ offset 0-তে index 0 (`bar+foo`) ও 9 (`foo+bar`) মেলে → `[0, 9]`। দ্বিতীয় case-এ দুটো `"word"` কখনো এক block-এ `good`+`best`-সহ জোগাড় হয় না → `[]`। তৃতীয় case-এ `bar+foo+the`-এর নানা ক্রমে index 6, 9, 12 মেলে → sort করে `[6, 9, 12]`। খালি `s`-এ `[]`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n · L)** worst case (n = `len(s)`, L = `word_len`) — `L`টা offset, প্রতিটায় `n/L` word, আর shrink-এ প্রতিটা word সর্বোচ্চ একবার বাদ; অনেক বিশ্লেষণে এটাকে O(n · L) ধরা হয়। নাইভ O(n · k) থেকে ভালো যখন k বড়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(k · L)** — `need` ও `window`-এ সর্বোচ্চ `k`টা আলাদা word, প্রতিটা দৈর্ঘ্য `L`।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- word পুনরাবৃত্তি ভুলে যাওয়া — set দিয়ে করলে `["word","word"]`-এর দুটো `word` ধরা পড়ে না; **Counter** লাগবে।
- সব offset না দেখা — শুধু offset 0 থেকে শুরু করলে যেসব valid block অন্য phase-এ শুরু হয় সেগুলো বাদ পড়ে; `range(word_len)`-এর প্রতিটা offset চাই।
- অচেনা word-এ window না ভাঙা — চেনা সীমার বাইরের word এলে `window`/`count`/`left` রিসেট না করলে ভুল ম্যাচ হয়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Minimum Window Substring (#20)-এর count-মেলানো sliding window — এখানে alphabet হলো word, window fixed-length, আর `L`টা phase আলাদা করে দেখা হয়। মূল frequency counting আসে Pattern 1 থেকে (Valid Anagram #3-এর বংশধর)। সম্পূর্ণ আলোচনা [../patterns.md](../patterns.md)-র Pattern 1-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Minimum Window Substring —