Problem link ও উৎস
- **Original source:** Classic frequency-counting / canonical-key exercise
- **Platform:** LeetCode —
- **Topic:** string / hash map
- **Difficulty:** Medium
- **Pattern:** frequency counting / canonical key (একই signature-এর word একসাথে bucket-এ)
- **Basic idea inherited from:** Valid anagram (problem 3) — count map; এখানে সেই count map-টাকেই bucket-এর key বানানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একগুচ্ছ word দেওয়া আছে (`strs`)। তোমার কাজ: যেসব word একে অপরের **anagram** (ঠিক একই অক্ষর, একই সংখ্যকবার, শুধু সাজানো আলাদা) তাদের একসাথে এক দলে রাখো। শেষে দলগুলোর একটা list ফেরত দাও। প্রতিটা word ঠিক একটা দলেই থাকবে।
```text
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
দল : ["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 (একটা খালি word): [""] -> [[""]]
Edge case 2 (একটাই word): ["a"] -> [["a"]]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো ডাকঘরে চিঠি বাছাই হচ্ছে। প্রতিটা চিঠির উপরে শুধু এলাকার pin code দেখা হয়, পুরো ঠিকানা পড়ে পড়ে চিঠিতে-চিঠিতে মেলানো হয় না। একই pin code-এর চিঠি একই ব্যাগে। এখানে signature-ই হলো pin code — গণনা মিললেই একই ব্যাগে (bucket) পড়ে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত হলো **Valid Anagram (problem 3)**-এর count map। ওখানে শিখেছিলে: দুটো word anagram **iff** তাদের অক্ষর-গণনা সমান। এখানে সেই গণনাকেই এক ধাপ এগিয়ে নিই — count map-টাকে একটা **canonical key** (একক পরিচয়) বানিয়ে dict-এ bucket হিসেবে ব্যবহার করি। anagram হলে key মিলবে, তাই একই bucket-এ পড়বে। গভীরে: [../../01-math-based-programming-fundamentals/03-counting-combinatorics/](../../01-math-based-programming-fundamentals/03-counting-combinatorics/README.md)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: anagram একটা **equivalence relation** — "একই multiset of characters" এই সম্পর্ক reflexive, symmetric, transitive। তাই word-গুলো ভেঙে যায় কতগুলো আলাদা শ্রেণিতে (equivalence class), আর প্রতিটা শ্রেণির একটা প্রতিনিধি (canonical form) আছে: তার অক্ষর-গণনার signature। দুটো word একই শ্রেণিতে **তখনই এবং কেবল তখনই** যখন তাদের signature এক।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **hash map (dict)**, যেখানে key = canonical signature (26-ঘরের count-এর tuple), value = সেই signature-ওয়ালা word-দের list। প্রতিটা word-এর জন্য একটা ছোট 26-দৈর্ঘ্যের count array।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রশ্ন আসলে "একই পরিচয়ের জিনিস একসাথে জড়ো করা" — এটাই hash map-এর জন্মগত কাজ: key দিয়ে average **O(1)**-এ bucket খুঁজে সেখানে append। tuple immutable বলে সেটা dict-এর key হতে পারে। প্রতিটা word-এর signature O(k)-তে (k = word-এর দৈর্ঘ্য) বানিয়ে সরাসরি bucket-এ ফেলা যায়, কোনো word-জোড়া তুলনা ছাড়াই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: এখনো group না-হওয়া word নাও, বাকি সবার সাথে এক-এক করে "anagram কিনা" check করো (problem 3-এর count-compare), যারা মেলে তাদের এক দলে নাও।
```text
groups = []
for word in strs:
placed = False
for g in groups:
if is_anagram(word, g[0]): # problem 3
g.append(word); placed = True; break
if not placed:
groups.append([word])
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা word-কে সব existing group-এর প্রতিনিধির সাথে তুলনা করতে হয় — worst case **O(n^2 · k)** (n word, প্রতিবার আগের সবার সাথে, প্রতিটা compare O(k))। অথচ signature একবার বানিয়ে dict-এ ফেললে তুলনার দরকারই নেই — hash সরাসরি ঠিক bucket-এ নিয়ে যায়, মোট O(n · k)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: anagram-দের মধ্যে word-জোড়া **তুলনা** করার দরকার নেই; বরং প্রতিটা word-কে তার **canonical signature**-এ রূপান্তর করো — anagram-রা আপনাআপনি একই signature পাবে। তখন grouping মানে শুধু "একই key-এর জিনিস একই বালতিতে ফেলা।"
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রতিটা word-এর জন্য 26-দৈর্ঘ্যের একটা count array বানাও (কোন অক্ষর কতবার)। সেই array-কে `tuple`-এ পরিণত করে dict-এর key বানাও। `setdefault(key, [])`-এ word append করো। সব word শেষ হলে dict-এর সব value-ই হলো group-গুলো। count-key ব্যবহারে signature বানানো O(k), তাই মোট O(n · k) — sort-key (`tuple(sorted(word))`) version-এর O(n · k log k)-এর চেয়ে দ্রুত।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কোন কোন word anagram তা মিলিয়ে দেখব" ভাবার বদলে ভাবো "প্রতিটা word-কে একটা অপরিবর্তনীয় পরিচয় (count signature) দেব, তারপর একই পরিচয়ের সব word এক bucket-এ পড়বে।" তুলনা গায়েব হয়ে grouping-টা একটা hash-map insert-এ নেমে আসে।
### ছবিতে বোঝা {#7-visual-explanation}
`["eat", "tea", "tan", "ate", "nat", "bat"]` — প্রতিটা word-এর signature বানিয়ে bucket-এ ফেলি:
```text
"eat" -> count a:1,e:1,t:1 (key K1) -> buckets{ K1:[eat] }
"tea" -> a:1,e:1,t:1 (key K1) -> buckets{ K1:[eat,tea] }
"tan" -> a:1,n:1,t:1 (key K2) -> buckets{ K1:[eat,tea], K2:[tan] }
"ate" -> a:1,e:1,t:1 (key K1) -> buckets{ K1:[eat,tea,ate], K2:[tan] }
"nat" -> a:1,n:1,t:1 (key K2) -> buckets{ K1:[eat,tea,ate], K2:[tan,nat] }
"bat" -> a:1,b:1,t:1 (key K3) -> buckets{ K1:[eat,tea,ate], K2:[tan,nat], K3:[bat] }
ফল: [[eat,tea,ate], [tan,nat], [bat]]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `["eat", "ate", "bat"]`:
1. `"eat"`: count → a:1,e:1,t:1; key `(...,1,...,1,...,1,...)`; dict খালি → নতুন bucket; `groups = {K_eat: ["eat"]}`।
2. `"ate"`: count → a:1,e:1,t:1; key একই `K_eat`; bucket-এ append → `{K_eat: ["eat","ate"]}`।
3. `"bat"`: count → a:1,b:1,t:1; key নতুন `K_bat`; নতুন bucket → `{K_eat:["eat","ate"], K_bat:["bat"]}`।
4. `list(groups.values())` → `[["eat","ate"], ["bat"]]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def group_anagrams(strs):
groups = {}
for word in strs:
count = [0] * 26 # 26 lowercase letter-এর গণনা
for ch in word:
count[ord(ch) - ord('a')] += 1
key = tuple(count) # count map-ই canonical key
groups.setdefault(key, []).append(word)
return list(groups.values())
# ---- tests ----
assert group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]) == \
[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
assert group_anagrams([""]) == [[""]] # খালি word
assert group_anagrams(["a"]) == [["a"]] # একটাই word
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `groups = {}` — signature → সেই signature-এর word-দের list।
- `count = [0] * 26` — প্রতিটা word-এর জন্য নতুন গণনা (ধরে নিচ্ছি lowercase a–z)।
- `count[ord(ch) - ord('a')] += 1` — অক্ষরটাকে 0–25 index-এ ফেলে গুনি।
- `key = tuple(count)` — list mutable, key হতে পারে না; tuple immutable, তাই dict-key হিসেবে ব্যবহারযোগ্য।
- `groups.setdefault(key, []).append(word)` — key থাকলে সেই bucket, নইলে নতুন খালি list বানিয়ে তাতে word ঢোকাই।
- `return list(groups.values())` — সব bucket-ই চূড়ান্ত group।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`["eat","tea","tan","ate","nat","bat"]`: `eat/tea/ate` একই count-key পেয়ে এক bucket; `tan/nat` আরেক bucket; `bat` আলাদা → `[["eat","tea","ate"],["tan","nat"],["bat"]]`, assert pass (Python dict insertion-order রাখে বলে ক্রম স্থির)। `[""]` → all-zero key → `[[""]]`; `["a"]` → `[["a"]]`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
প্রতিটা word-এর 26-count signature-কে string key বানিয়ে `Map`-এ bucket।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
// group words that are anagrams (count signature key)
function groupAnagrams(strs) {
const groups = new Map();
for (const word of strs) {
const count = new Array(26).fill(0); // 26 lowercase letter গণনা
for (const ch of word) count[ch.charCodeAt(0) - 97]++;
const key = count.join("#"); // count map-ই canonical key
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(word);
}
return [...groups.values()];
}
// ---- test cases (example + edge) ----
assert(eq(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]),
[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]), "classic");
assert(eq(groupAnagrams([""]), [[""]]), "empty-word"); // edge
assert(eq(groupAnagrams(["a"]), [["a"]]), "single"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** JS-এ array reference দিয়ে compare হয়, তাই count array সরাসরি Map key হতে পারে না — `count.join("#")` দিয়ে string key বানাও (separator `#` ambiguity ঠেকায়, যেমন `[1,11]` বনাম `[11,1]`)। `Map` insertion-order রাখে বলে group-এর ক্রম স্থির।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function groupAnagrams(strs: string[]): string[][] {
const groups = new Map