006 — Group Anagrams¶

Source¶

Original source: Classic capstone interview problem (canonical-key bucketing)
Platform: LeetCode — https://leetcode.com/problems/group-anagrams/
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।

1. Problem in simple words¶

তোমাকে কতগুলো word দেওয়া আছে। দুটো word anagram যদি একটার অক্ষরগুলো সাজিয়ে অন্যটা বানানো যায় (যেমন eat, tea, ate — সবগুলোতে একই অক্ষর, শুধু ক্রম আলাদা)। তোমার কাজ: যেসব word একে অপরের anagram, তাদের একই দলে রাখো; আলাদা দলগুলোর একটা list ফেরত দাও।

words : ["eat", "tea", "tan", "ate", "nat", "bat"]
groups: [["eat","tea","ate"], ["tan","nat"], ["bat"]]

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) এখানে নিখুঁত।

6. Real-life analogy¶

ভাবো তুমি অনেকগুলো চিঠি বাছাই করছ, আর প্রতিটার উপর শহরের নাম লেখা। তুমি প্রতিটা শহরের জন্য একটা করে আলাদা বাক্স (bucket) রাখো; চিঠি এলে শহরের নাম দেখে সরাসরি ঠিক বাক্সে ফেলে দাও — সব চিঠি একে একে অন্য সব চিঠির সাথে মেলানোর দরকার নেই। এখানে "শহরের নাম" = anagram fingerprint, "বাক্স" = hashmap-এর bucket।

7. Visual explanation¶

["eat","tea","tan","ate"] bucket-এ পড়ছে (key = sorted অক্ষর):

"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"]]

8. Example input and output¶

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"]]

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা word-কে এখনও-পর্যন্ত-বানানো প্রতিটা দলের একটা প্রতিনিধির সাথে মিলিয়ে দেখো — anagram হলে সেই দলে ঢোকাও, নাহলে নতুন দল খোলো।

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-এ গলে যায়।

14. Step-by-step dry run¶

Input ["bat","tab","cat"] (key = sorted):

শুরু: buckets = {}
"bat" → key "abt" → {"abt": ["bat"]}
"tab" → key "abt" → {"abt": ["bat","tab"]}
"cat" → key "act" → {"abt": ["bat","tab"], "act": ["cat"]}
শেষ: list(buckets.values()) = [["bat","tab"], ["cat"]]

15. Python solution¶

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 করে তুলনা।

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!।

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-এ ক্রম-নিরপেক্ষ তুলনা করা উচিত।

21. Which basic problem this inherits from¶

ভিত্তি: anagram detection / canonical string রূপ (02 strings, ../../02-arrays-and-strings/) + frequency/group hashmap (05 hashing, ../../05-hashing/)। "Valid Anagram" (দুটো word মেলানো)-র সরাসরি একটা ধাপ উপরে এটা — দুইয়ের বদলে n-টা গোছানো।

22. Similar harder problems¶

Group Shifted Strings (shift-প্যাটার্ন দিয়ে canonical key) — https://leetcode.com/problems/group-shifted-strings/
Find All Anagrams in a String (window + count) — https://leetcode.com/problems/find-all-anagrams-in-a-string/
Valid Anagram (এক-জোড়া version) — https://leetcode.com/problems/valid-anagram/

23. Pattern learned¶

Canonical key + hashmap bucketing: প্রতিটা item-কে এমন একটা key-তে অনুবাদ করো যাতে "একই দল" মানেই "একই key", তারপর hashmap-এ এক পাসে bucket করো — pairwise তুলনা মুছে O(n)-এ গোছানো। গোছানো/ডিডুপ-ধরনের বহু problem-এর core।

24. Final summary¶

ভবিষ্যতের আমাকে: "একই বৈশিষ্ট্যের জিনিস দলে দলে ভাগ করো" শুনলেই canonical-key + hashmap মনে করবে। আসল চাল হলো সঠিক key বেছে নেওয়া (এখানে sorted অক্ষর বা count tuple)। defaultdict(list) ব্যবহার করলে কোড দু'লাইনে নেমে আসে। দল-ক্রম গুরুত্বহীন — সেটা মুখে বলে দিও।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।