Problem link ও উৎস
- **Original source:** Classic canonical-key grouping exercise
- **Platform:** LeetCode —
- **Topic:** hash map (grouping)
- **Difficulty:** Medium
- **Pattern:** grouping by canonical key
- **Basic idea inherited from:** frequency counting — একই count profile মানে একই দল
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একগুচ্ছ string `words` দেওয়া আছে। যেসব string একে অপরের **anagram** (অর্থাৎ ঠিক একই অক্ষর, শুধু সাজানো আলাদা), তাদের একই দলে জড়ো করতে হবে। ফেরত দিতে হবে দলগুলোর একটা list; দলগুলোর ক্রম যেকোনো হতে পারে।
```text
["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"]] (দলের ক্রম যেকোনো)
Input : [""] Output: [[""]]
Input : ["a"] Output: [["a"]]
Input : ["abc","bca","cab","xyz"]
Output: [["abc","bca","cab"], ["xyz"]]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো ডাকঘরে অনেক চিঠি এসেছে, প্রতিটায় এলাকার pin code লেখা। তুমি চিঠিগুলো একে অপরের সাথে মিলিয়ে দেখো না — শুধু pin code পড়ে সেই code-এর বাক্সে ফেলে দাও। এক রাউন্ডেই সব চিঠি নিজ নিজ এলাকায় ভাগ হয়ে যায়। এখানে pin code-ই canonical key, আর বাক্সগুলো hash map-এর bucket।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে **frequency counting**-এর উপর (Valid Anagram, #3)। সেখানে শিখেছ দুটো string anagram কি না বোঝা যায় তাদের অক্ষরের count profile মিলিয়ে। এখানে সেই profile-কেই **key** বানাচ্ছি: একই profile-ওয়ালা সব string এক bucket-এ। [../patterns.md](../patterns.md)-তে এটাই Pattern 3 — *grouping by canonical key*।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: anagram একটা **equivalence relation** — "একই অক্ষরসেট" দিয়ে সব string কে শ্রেণিতে ভাগ করা যায়। প্রতিটা শ্রেণির জন্য একটা **canonical form** (একটাই প্রতিনিধি রূপ) বেছে নিলে, একই শ্রেণির সব সদস্য সেই একই রূপে এসে দাঁড়ায়। দুটো সরল canonical রূপ: (ক) অক্ষরগুলো sort করা string, বা (খ) 26টা অক্ষরের count-এর tuple।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **hash map**, যেখানে key = canonical form আর value = সেই form-এ পড়া word-দের list। Python-এ `collections.defaultdict(list)` ব্যবহার করলে নতুন key-তে list নিজে থেকেই তৈরি হয়ে যায়, তাই "key আছে কি না" আগে check করতে হয় না।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
আমরা চাই "একই key-ওয়ালা জিনিসগুলো একসাথে জমা হোক" — hash map ঠিক এই কাজটাই গড়ে O(1)-এ করে। প্রতিটা word-এর key হিসেব করে সরাসরি তার bucket-এ append করি; word-গুলোকে জোড়ায় জোড়ায় মিলিয়ে দেখার দরকার নেই। List হলে দল খুঁজতে প্রতিবার scan করতে হতো — O(n^2)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা এখনো-দলহীন word নাও, বাকি সব word-এর সাথে মিলিয়ে দেখো anagram কি না, মিললে একই দলে রাখো।
```text
প্রতিটা word w-র জন্য (যদি আগে দলভুক্ত না হয়):
নতুন দল শুরু করো
বাকি প্রতিটা word u-র জন্য:
w আর u anagram হলে দলে যোগ করো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা word-কে বাকি সবার সাথে মেলানো মানে **O(n^2)** জোড়া তুলনা, আর প্রতিটা তুলনায় আবার অক্ষর গোনা/sort করার খরচ। আসল অপচয়: আমরা একই word বারবার পরীক্ষা করছি, যদিও প্রতিটা word-এর "পরিচয়" (canonical key) একবার হিসেব করলেই সব ঠিক জায়গায় বসে যেত।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একই দলের সব সদস্য একটাই canonical key-তে নেমে আসে।** তাই দল বানানোর জন্য word-দের পরস্পরের সাথে তুলনা করার দরকার নেই — প্রতিটা word একবার normalize করো, hash map নিজেই সমান key-ওয়ালাদের একসাথে জড়ো করবে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
সব word-এর উপর একবার হাঁটো। প্রতিটায় canonical key (sorted অক্ষর, বা count-tuple) হিসেব করে সরাসরি `defaultdict(list)`-এর সেই key-তে append করো। শেষে map-এর সব value-ই হলো দলগুলো। O(n · k) — যেখানে k হলো গড় word দৈর্ঘ্য (sort-এর জন্য O(k log k), count-tuple হলে O(k))।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** *জিনিস দুটোকে তুলনা কোরো না — প্রত্যেককে একটা সাধারণ রূপে অনুবাদ করো, hash map-কে দল বানাতে দাও।* এই tweak O(n^2) pairwise comparison-কে O(n) bucketing-এ নামিয়ে আনে। "group", "bucket", "which are equivalent" শুনলেই এই চাল মনে পড়া চাই।
### ছবিতে বোঝা {#7-visual-explanation}
key = sorted অক্ষর। প্রতিটা word তার key-র bucket-এ পড়ছে:
```text
"eat" → sorted "aet" → groups["aet"] = ["eat"]
"tea" → sorted "aet" → groups["aet"] = ["eat","tea"]
"tan" → sorted "ant" → groups["ant"] = ["tan"]
"ate" → sorted "aet" → groups["aet"] = ["eat","tea","ate"]
"nat" → sorted "ant" → groups["ant"] = ["tan","nat"]
"bat" → sorted "abt" → groups["abt"] = ["bat"]
```
তিনটা bucket তৈরি হলো: `"aet"`, `"ant"`, `"abt"` — এগুলোর value-ই উত্তর।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `["abc", "bca", "xyz"]`:
1. শুরু: `groups = {}` (খালি defaultdict)।
2. `"abc"`: key = `"abc"` → `groups = {"abc": ["abc"]}`।
3. `"bca"`: sorted → `"abc"` → `groups = {"abc": ["abc", "bca"]}`।
4. `"xyz"`: sorted → `"xyz"` → `groups = {"abc": ["abc","bca"], "xyz": ["xyz"]}`।
5. উত্তর: `[["abc","bca"], ["xyz"]]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list) # canonical key -> word list
for w in words:
key = "".join(sorted(w)) # একই অক্ষর → একই key
groups[key].append(w)
return list(groups.values())
def normalize(groups): # order-independent তুলনার জন্য
return sorted(sorted(g) for g in groups)
# ---- tests ----
assert normalize(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])) == \
[["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
assert normalize(group_anagrams([""])) == [[""]]
assert normalize(group_anagrams(["a"])) == [["a"]]
assert normalize(group_anagrams(["abc", "bca", "cab", "xyz"])) == \
[["abc", "bca", "cab"], ["xyz"]]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `groups = defaultdict(list)` — নতুন key চাইলেই খালি list তৈরি হবে, তাই "key আছে?" check লাগে না।
- `for w in words` — প্রতিটা word একবার দেখি।
- `key = "".join(sorted(w))` — অক্ষর sort করে canonical রূপ বানাই; anagram-রা একই রূপ পায়।
- `groups[key].append(w)` — word-কে তার দলের bucket-এ ফেলি।
- `return list(groups.values())` — সব bucket-ই হলো দলগুলো।
- `normalize(...)` — test helper: প্রতিটা দল sort, তারপর দলগুলো sort, যাতে ক্রম-নিরপেক্ষভাবে মেলানো যায় (assert স্থিতিশীল থাকে)।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`["eat","tea","tan","ate","nat","bat"]`-এ তিনটা key তৈরি হয়: `"aet"` (eat, tea, ate), `"ant"` (tan, nat), `"abt"` (bat)। `normalize` প্রতিটা দল sort করে আর দলগুলোকেও sort করে দেয় `[["ate","eat","tea"], ["bat"], ["nat","tan"]]`। `[""]`-এর key খালি string `""` → `[[""]]`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n · k log k)** — n হলো word সংখ্যা, k হলো গড় দৈর্ঘ্য; প্রতিটা word-এ sort O(k log k)। count-tuple key ব্যবহার করলে নামে **O(n · k)**।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n · k)** — সব word আর তাদের key hash map-এ জমা থাকে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- canonical key অসংগত বানানো — একটা word sort করা আর আরেকটা না করা; সব word-এ একই rule খাটাতে হবে।
- `sorted(w)`-এর ফল list, সেটাকে `"".join(...)` না করে সরাসরি key বানানো — list hashable নয়, তাই dict key হতে পারবে না (string বা tuple লাগবে)।
- দলের ভেতরের ক্রম নিয়ে assert লেখা — insertion order-নির্ভর; test স্থিতিশীল রাখতে দল sort করে মেলাও।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Valid Anagram (#3)-এর frequency/count profile। সেখানে দুটো string-এর profile মেলানো হয়; এখানে সেই profile-কে key বানিয়ে n-টা string একসাথে দলবদ্ধ করা হয়। পুরো চাল [../patterns.md](../patterns.md)-র Pattern 3-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Valid Anagram —