Problem link ও উৎস
- **Original source:** Classic capstone interview problem (canonical-key bucketing)
- **Platform:** LeetCode —
- **Topic:** strings + hashing
- **Difficulty:** Medium
- **Pattern:** Canonical key + hashmap bucketing
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **02 strings** (একটা word-কে এমনভাবে রূপান্তর করা যাতে সব anagram একই রূপ পায় — sort বা letter-count) আর **05 hashing** (সেই রূপটাকে dictionary key বানিয়ে এক bucket-এ জড়ো করা)। দুই tool জোড়া লাগলেই এই problem।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে কতগুলো word দেওয়া আছে। দুটো word **anagram** যদি একটার অক্ষরগুলো সাজিয়ে অন্যটা বানানো যায় (যেমন `eat`, `tea`, `ate` — সবগুলোতে একই অক্ষর, শুধু ক্রম আলাদা)। তোমার কাজ: যেসব word একে অপরের anagram, তাদের একই দলে রাখো; আলাদা দলগুলোর একটা list ফেরত দাও।
```text
words : ["eat", "tea", "tan", "ate", "nat", "bat"]
groups: [["eat","tea","ate"], ["tan","nat"], ["bat"]]
```
### Input ও output {#8-example-input-and-output}
```text
Input : ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"], ["tan","nat"], ["bat"]] # দলগুলোর ক্রম গুরুত্বহীন
Edge case 1 (খালি input): Input: [] -> Output: []
Edge case 2 (একটা খালি string): Input: [""] -> Output: [[""]]
Edge case 3 (কোনো anagram নেই): Input: ["abc","def"] -> Output: [["abc"],["def"]]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি অনেকগুলো চিঠি বাছাই করছ, আর প্রতিটার উপর শহরের নাম লেখা। তুমি প্রতিটা শহরের জন্য একটা করে আলাদা বাক্স (bucket) রাখো; চিঠি এলে শহরের নাম দেখে সরাসরি ঠিক বাক্সে ফেলে দাও — সব চিঠি একে একে অন্য সব চিঠির সাথে মেলানোর দরকার নেই। এখানে "শহরের নাম" = anagram fingerprint, "বাক্স" = hashmap-এর bucket।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **02 strings** থেকে: একটা word-কে এমন একটা **canonical (আদর্শ) রূপ**-এ আনা যাতে সব anagram-এর রূপ এক হয় — হয় অক্ষর sort করে (`"eat" -> "aet"`), নয় প্রতিটা অক্ষরের গণনা দিয়ে।
- **05 hashing** থেকে: সেই canonical রূপটাকে একটা dictionary-র **key** বানিয়ে, একই key-র সব word এক list-এ জড়ো করা — O(1)-এ "এই দল আগে দেখেছি কি না" দেখা।
একা string-জ্ঞান দেয় anagram চেনার রূপ; একা hashing দেয় তাৎক্ষণিক bucketing। দুটো মিললে দ্রুত গোছানো।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **anagram-রা একটা equivalence class তৈরি করে** — "একই অক্ষর-সমষ্টি" সম্পর্কটা reflexive, symmetric, transitive। প্রতিটা class-কে একটা unique fingerprint দিলেই হয়, আর দুটো word একই class-এ পড়ে ঠিক তখনই যখন তাদের fingerprint সমান। sorted অক্ষর বা 26-অক্ষরের count tuple — দুটোই এমন fingerprint।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **hashmap** (Python-এ `dict`/`defaultdict`), যার key = word-এর canonical রূপ, value = সেই key-র সব word-এর list। এটাই 05 hashing-এর কেন্দ্রীয় tool — same-key জিনিস তাৎক্ষণিক এক জায়গায় জমে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
আমরা চাই: "এই word-এর fingerprint কি আগে দেখেছি? দেখে থাকলে সেই দলে যোগ করো, নাহলে নতুন দল খোলো" — আর এই lookup+insert গড়ে **O(1)**। hashmap ঠিক এটাই দেয়। list বা nested loop দিয়ে প্রতিটা নতুন word-কে সব পুরনো দলের সাথে মিলিয়ে দেখলে O(n^2) হয়ে যেত; hashmap সেই খরচ মুছে দেয়। এজন্যই strings (02) + hashing (05) এখানে নিখুঁত।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা word-কে এখনও-পর্যন্ত-বানানো প্রতিটা দলের একটা প্রতিনিধির সাথে মিলিয়ে দেখো — anagram হলে সেই দলে ঢোকাও, নাহলে নতুন দল খোলো।
```text
groups = []
for w in words:
placed = False
for g in groups:
if is_anagram(w, g[0]):
g.append(w); placed = True; break
if not placed:
groups.append([w])
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা নতুন word-এর জন্য সব পুরনো দল ঘুরে দেখা — সবচেয়ে খারাপ ক্ষেত্রে (সব আলাদা) **O(n^2)** তুলনা, আর প্রতিটা `is_anagram`-ও O(k)। বড় input-এ ধীর। মূল অপচয়: একই দল আছে কি না খুঁজতে বারবার রৈখিক scan — যেটা hashmap (05) O(1)-এ করে দেয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **প্রতিটা দলকে একটা unique key দিয়ে চেনা যায় — anagram-দের canonical রূপ এক।** তাই "এই word কোন দলে?" প্রশ্নের উত্তর খুঁজতে দল ঘুরতে হয় না; word থেকে সরাসরি key বানিয়ে hashmap-এ এক ধাপে পৌঁছানো যায়। এটাই O(n^2) → O(n·k) করে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রতিটা word-এর জন্য একটা canonical key বানাও — sorted অক্ষর (`"".join(sorted(w))`) সবচেয়ে সহজ। সেই key দিয়ে hashmap-এ word-টা append করো (`defaultdict(list)` থাকলে দল নিজে নিজে খুলে যায়)। সব word দেখা হলে hashmap-এর সব value-ই হলো দলগুলো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কোন word কোন word-এর anagram তা মেলাব" ভাবার বদলে ভাবো "প্রতিটা word-কে তার canonical রূপে অনুবাদ করি, একই রূপ মানেই একই বাক্স।" pairwise তুলনা একটা single-pass bucketing-এ গলে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`["eat","tea","tan","ate"]` bucket-এ পড়ছে (key = sorted অক্ষর):
```text
"eat" -> key "aet" -> { "aet": ["eat"] }
"tea" -> key "aet" -> { "aet": ["eat","tea"] }
"tan" -> key "ant" -> { "aet": ["eat","tea"], "ant": ["tan"] }
"ate" -> key "aet" -> { "aet": ["eat","tea","ate"], "ant": ["tan"] }
ফল: [["eat","tea","ate"], ["tan"]]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `["bat","tab","cat"]` (key = sorted):
1. শুরু: `buckets = {}`
2. `"bat"` → key `"abt"` → `{"abt": ["bat"]}`
3. `"tab"` → key `"abt"` → `{"abt": ["bat","tab"]}`
4. `"cat"` → key `"act"` → `{"abt": ["bat","tab"], "act": ["cat"]}`
5. শেষ: `list(buckets.values())` = `[["bat","tab"], ["cat"]]`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import defaultdict
def group_anagrams(words):
buckets = defaultdict(list) # key (canonical রূপ) -> word-দের list
for w in words:
key = "".join(sorted(w)) # anagram-দের sorted রূপ এক
buckets[key].append(w) # ঠিক বাক্সে ফেলো (দল নিজে খোলে)
return list(buckets.values()) # সব বাক্স = সব দল
# ---- helper (test-এ ক্রম-নিরপেক্ষ তুলনা) ----
def normalize(groups):
# প্রতিটা দল sort, তারপর দলগুলোকেও sort -> ক্রম ভুলে তুলনা
return sorted(sorted(g) for g in groups)
# ---- tests ----
assert normalize(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])) == \
normalize([["bat"], ["nat", "tan"], ["ate", "eat", "tea"]])
assert group_anagrams([]) == [] # খালি input
assert group_anagrams([""]) == [[""]] # একটা খালি string
assert normalize(group_anagrams(["abc", "def"])) == normalize([["abc"], ["def"]])
assert normalize(group_anagrams(["a", "a"])) == normalize([["a", "a"]]) # ডুপ্লিকেট একসাথে
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `buckets = defaultdict(list)` — নতুন key দেখলে আপনাআপনি খালি list খোলে, তাই "দল আছে কি?" চেক লাগে না।
- `for w in words` — প্রতিটা word একবার করে দেখি (single pass)।
- `key = "".join(sorted(w))` — word-এর অক্ষর sort করে canonical fingerprint (02 strings)।
- `buckets[key].append(w)` — সেই fingerprint-এর বাক্সে word ঢোকাও — গড়ে O(1) (05 hashing)।
- `return list(buckets.values())` — প্রতিটা value হলো এক-একটা anagram দল।
- `normalize` (শুধু test-এর জন্য) — দল ও দল-ভেতরের ক্রম গুরুত্বহীন, তাই দু'স্তরে sort করে তুলনা।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`["eat","tea","tan","ate","nat","bat"]`-এ key-গুলো হয় `"aet"`(eat/tea/ate), `"ant"`(tan/nat), `"abt"`(bat) — তিনটে বাক্স। `values()` দেয় তিন দল; `normalize` দিয়ে ক্রম-নিরপেক্ষ তুলনায় assert pass। খালি input, খালি-string, ডুপ্লিকেট case-ও সঠিক। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n · k log k)** — `n` word, প্রতিটার দৈর্ঘ্য `k`; key বানাতে `sorted(w)` = O(k log k)। count-key (26-length) ব্যবহার করলে O(n · k)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n · k)** — hashmap-এ সব word ও তাদের key জমা; output-ও সব word ধরে রাখে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- key হিসেবে `sorted(w)` (একটা list) সরাসরি ব্যবহার করা — list hashable না, তাই `"".join(...)` করে string বানাতে হয়।
- খালি string-কে আলাদা ভাবা — আসলে এর key `""`, স্বাভাবিকভাবেই এক দলে পড়ে; আলাদা handling লাগে না।
- দলগুলোর ক্রম নির্দিষ্ট ধরে নেওয়া — output-এর দল-ক্রম গুরুত্বহীন, তাই tester-এ ক্রম-নিরপেক্ষ তুলনা করা উচিত।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: anagram detection / canonical string রূপ (02 strings, [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)) + frequency/group hashmap (05 hashing, [../../05-hashing/](../../05-hashing/README.md))। "Valid Anagram" (দুটো word মেলানো)-র সরাসরি একটা ধাপ উপরে এটা — দুইয়ের বদলে n-টা গোছানো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Group Shifted Strings (shift-প্যাটার্ন দিয়ে canonical key) —