006 — Group Anagrams¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

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।

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

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

উদাহরণ

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

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

চেনা উদাহরণে বোঝা¶

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

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

এই 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। দুটো মিললে দ্রুত গোছানো।

ভেতরের যুক্তি¶

লুকানো logic: anagram-রা একটা equivalence class তৈরি করে — "একই অক্ষর-সমষ্টি" সম্পর্কটা reflexive, symmetric, transitive। প্রতিটা class-কে একটা unique fingerprint দিলেই হয়, আর দুটো word একই class-এ পড়ে ঠিক তখনই যখন তাদের fingerprint সমান। sorted অক্ষর বা 26-অক্ষরের count tuple — দুটোই এমন fingerprint।

কী দিয়ে তথ্য রাখব¶

একটা hashmap (Python-এ dict/defaultdict), যার key = word-এর canonical রূপ, value = সেই key-র সব word-এর list। এটাই 05 hashing-এর কেন্দ্রীয় tool — same-key জিনিস তাৎক্ষণিক এক জায়গায় জমে।

এটি কেন উপযুক্ত¶

আমরা চাই: "এই word-এর fingerprint কি আগে দেখেছি? দেখে থাকলে সেই দলে যোগ করো, নাহলে নতুন দল খোলো" — আর এই lookup+insert গড়ে O(1)। hashmap ঠিক এটাই দেয়। list বা nested loop দিয়ে প্রতিটা নতুন word-কে সব পুরনো দলের সাথে মিলিয়ে দেখলে O(n^2) হয়ে যেত; hashmap সেই খরচ মুছে দেয়। এজন্যই strings (02) + hashing (05) এখানে নিখুঁত।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: প্রতিটা 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])

কোথায় বেশি কাজ হচ্ছে¶

প্রতিটা নতুন word-এর জন্য সব পুরনো দল ঘুরে দেখা — সবচেয়ে খারাপ ক্ষেত্রে (সব আলাদা) O(n^2) তুলনা, আর প্রতিটা is_anagram-ও O(k)। বড় input-এ ধীর। মূল অপচয়: একই দল আছে কি না খুঁজতে বারবার রৈখিক scan — যেটা hashmap (05) O(1)-এ করে দেয়।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: প্রতিটা দলকে একটা unique key দিয়ে চেনা যায় — anagram-দের canonical রূপ এক। তাই "এই word কোন দলে?" প্রশ্নের উত্তর খুঁজতে দল ঘুরতে হয় না; word থেকে সরাসরি key বানিয়ে hashmap-এ এক ধাপে পৌঁছানো যায়। এটাই O(n^2) → O(n·k) করে।

আরও কম কাজে সমাধান¶

প্রতিটা word-এর জন্য একটা canonical key বানাও — sorted অক্ষর ("".join(sorted(w))) সবচেয়ে সহজ। সেই key দিয়ে hashmap-এ word-টা append করো (defaultdict(list) থাকলে দল নিজে নিজে খুলে যায়)। সব word দেখা হলে hashmap-এর সব value-ই হলো দলগুলো।

ভাবনার পরিবর্তন¶

মোচড়: "কোন word কোন word-এর anagram তা মেলাব" ভাবার বদলে ভাবো "প্রতিটা word-কে তার canonical রূপে অনুবাদ করি, একই রূপ মানেই একই বাক্স।" pairwise তুলনা একটা single-pass bucketing-এ গলে যায়।

ছবিতে বোঝা¶

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

ছোট input-এ ধাপে ধাপে¶

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

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

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 মিলিয়ে দেখা¶

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

খরচ ও সাধারণ ভুল¶

সময়¶

O(n · k log k) — n word, প্রতিটার দৈর্ঘ্য k; key বানাতে sorted(w) = O(k log k)। count-key (26-length) ব্যবহার করলে O(n · k)।

অতিরিক্ত জায়গা¶

O(n · k) — hashmap-এ সব word ও তাদের key জমা; output-ও সব word ধরে রাখে।

যে ভুলগুলো এড়াতে হবে¶

key হিসেবে sorted(w) (একটা list) সরাসরি ব্যবহার করা — list hashable না, তাই "".join(...) করে string বানাতে হয়।
খালি string-কে আলাদা ভাবা — আসলে এর key "", স্বাভাবিকভাবেই এক দলে পড়ে; আলাদা handling লাগে না।
দলগুলোর ক্রম নির্দিষ্ট ধরে নেওয়া — output-এর দল-ক্রম গুরুত্বহীন, তাই tester-এ ক্রম-নিরপেক্ষ তুলনা করা উচিত।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

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

পরের অনুশীলন¶

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/

কৌশলটি মনে রাখুন¶

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

নিজেকে যাচাই করুন¶

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

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