017 — Group Anagrams

Problem link ও উৎস

• Original source: Classic frequency-counting / canonical-key exercise
• Platform: LeetCode — https://leetcode.com/problems/group-anagrams/
• 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 বানানো

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

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

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

উদাহরণ

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
দল   : ["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 (একটা খালি word): [""]  -> [[""]]
Edge case 2 (একটাই word):     ["a"] -> [["a"]]

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

ভাবো ডাকঘরে চিঠি বাছাই হচ্ছে। প্রতিটা চিঠির উপরে শুধু এলাকার pin code দেখা হয়, পুরো ঠিকানা পড়ে পড়ে চিঠিতে-চিঠিতে মেলানো হয় না। একই pin code-এর চিঠি একই ব্যাগে। এখানে signature-ই হলো pin code — গণনা মিললেই একই ব্যাগে (bucket) পড়ে।

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

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

ভিত হলো 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/।

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

লুকানো logic: anagram একটা equivalence relation — "একই multiset of characters" এই সম্পর্ক reflexive, symmetric, transitive। তাই word-গুলো ভেঙে যায় কতগুলো আলাদা শ্রেণিতে (equivalence class), আর প্রতিটা শ্রেণির একটা প্রতিনিধি (canonical form) আছে: তার অক্ষর-গণনার signature। দুটো word একই শ্রেণিতে তখনই এবং কেবল তখনই যখন তাদের signature এক।

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

একটা hash map (dict), যেখানে key = canonical signature (26-ঘরের count-এর tuple), value = সেই signature-ওয়ালা word-দের list। প্রতিটা word-এর জন্য একটা ছোট 26-দৈর্ঘ্যের count array।

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

প্রশ্ন আসলে "একই পরিচয়ের জিনিস একসাথে জড়ো করা" — এটাই hash map-এর জন্মগত কাজ: key দিয়ে average O(1)-এ bucket খুঁজে সেখানে append। tuple immutable বলে সেটা dict-এর key হতে পারে। প্রতিটা word-এর signature O(k)-তে (k = word-এর দৈর্ঘ্য) বানিয়ে সরাসরি bucket-এ ফেলা যায়, কোনো word-জোড়া তুলনা ছাড়াই।

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

প্রথম সরল উপায়

প্রথম সরল চিন্তা: এখনো group না-হওয়া word নাও, বাকি সবার সাথে এক-এক করে "anagram কিনা" check করো (problem 3-এর count-compare), যারা মেলে তাদের এক দলে নাও।

উদাহরণ

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

কোথায় বেশি কাজ হচ্ছে

প্রতিটা word-কে সব existing group-এর প্রতিনিধির সাথে তুলনা করতে হয় — worst case O(n^2 · k) (n word, প্রতিবার আগের সবার সাথে, প্রতিটা compare O(k))। অথচ signature একবার বানিয়ে dict-এ ফেললে তুলনার দরকারই নেই — hash সরাসরি ঠিক bucket-এ নিয়ে যায়, মোট O(n · k)।

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

মূল observation: anagram-দের মধ্যে word-জোড়া তুলনা করার দরকার নেই; বরং প্রতিটা word-কে তার canonical signature-এ রূপান্তর করো — anagram-রা আপনাআপনি একই signature পাবে। তখন grouping মানে শুধু "একই key-এর জিনিস একই বালতিতে ফেলা।"

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

প্রতিটা 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)-এর চেয়ে দ্রুত।

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

মোচড়: "কোন কোন word anagram তা মিলিয়ে দেখব" ভাবার বদলে ভাবো "প্রতিটা word-কে একটা অপরিবর্তনীয় পরিচয় (count signature) দেব, তারপর একই পরিচয়ের সব word এক bucket-এ পড়বে।" তুলনা গায়েব হয়ে grouping-টা একটা hash-map insert-এ নেমে আসে।

ছবিতে বোঝা

["eat", "tea", "tan", "ate", "nat", "bat"] — প্রতিটা word-এর signature বানিয়ে bucket-এ ফেলি:

উদাহরণ

"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-এ ধাপে ধাপে

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

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

Python

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

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

• 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 মিলিয়ে দেখা

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

প্রতিটা 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

TypeScript

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const word of strs) {
    const count: number[] = new Array<number>(26).fill(0);
    for (const ch of word) count[ch.charCodeAt(0) - 97]++;
    const key: string = count.join("#");
    const bucket = groups.get(key);
    if (bucket) bucket.push(word);
    else groups.set(key, [word]);
  }
  return [...groups.values()];
}
function expectArr(actual: string[][], exp: string[][], msg = ""): void {
  if (JSON.stringify(actual) !== JSON.stringify(exp))
    throw new Error(`FAIL ${msg}: got ${JSON.stringify(actual)}`);
}
expectArr(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]),
          [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]], "classic");
expectArr(groupAnagrams([""]), [[""]], "empty-word");
console.log("সব TS test pass!");

TS টীকা: Map<string, string[]> দিয়ে key/bucket টাইপ পাকা; groups.get(key) ফেরত দেয় string[] | undefined, তাই if (bucket) narrow করে নিরাপদে push — undefined-এ push করার bug compile-time-এ আটকায়।

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

সময়

O(n · k) — n = word সংখ্যা, k = সবচেয়ে বড় word-এর দৈর্ঘ্য; প্রতিটা word-এর signature O(k)-তে বানাই, dict insert average O(k) (key hash)। sort-key version হলে O(n · k log k)।

অতিরিক্ত জায়গা

O(n · k) — output-এ সব word একবার করে রাখা; dict-এর key-গুলোও মিলিয়ে word-গুলোর মোট আকারের সমানুপাতিক।

যে ভুলগুলো এড়াতে হবে

• count array-র বদলে শুধু string concat করে key বানানো (যেমন "a1e1t1") — সাবধান না হলে "a11" বনাম "a1b1"-এর মতো ambiguity আসতে পারে; tuple/seperator ব্যবহার নিরাপদ।
• list-কে সরাসরি dict-key বানানোর চেষ্টা — list unhashable, error; tuple-এ পরিণত করতে হয়।
• শুধু lowercase ধরে ord(ch) - ord('a') লেখা যখন input-এ uppercase/space থাকতে পারে — তখন আগে normalize করো বা tuple(sorted(word)) key ব্যবহার করো।

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

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

ভিত্তি: Valid Anagram (#3)-এর count map — সেই গণনাকেই এখানে bucket-key বানানো হয়েছে। chapter-এর ../patterns.md-এর "Pattern 5 — Frequency Counting" দেখো; সেখানেই canonical-key দিয়ে group করার idea-টা সরাসরি আছে।

পরের অনুশীলন

• Valid Anagram (ভিত্তি count-compare) — https://leetcode.com/problems/valid-anagram/ (#3)
• Find All Anagrams in a String (sliding window + count) — https://leetcode.com/problems/find-all-anagrams-in-a-string/
• Group Shifted Strings (আলাদা canonical key) — https://leetcode.com/problems/group-shifted-strings/

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

Canonical key / frequency bucketing: "একই-রকম জিনিস একসাথে group করো" দেখলে প্রতিটা item-কে একটা অপরিবর্তনীয় signature-এ রূপান্তর করো (anagram-এ count map), তারপর hash map-এ একই key-এর সব item এক bucket-এ ফেলো — তুলনা ছাড়া, O(n · k)।

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

ভবিষ্যতের আমাকে: "anagram group = প্রতিটা word-এর count signature বানাও, একই signature এক bucket।" "anagram অনুযায়ী group" বা "একই pattern-এর জিনিস জড়ো করা" দেখলেই canonical-key + hash map মনে করবে — তুলনা নয়, signature; O(n · k)।

কোথায় কাজে লাগে

• Canonical-key dedup: ভিন্ন রূপে আসা কিন্তু একই অর্থের data এক bucket-এ জড়ো করা (যেমন normalized form দিয়ে grouping)।
• Search/indexing: anagram বা rearranged query একই index entry-তে map করা।
• Spell-check / suggestions: একই অক্ষর-সেটের শব্দগুলো একসাথে রেখে দ্রুত suggestion।
• Plagiarism/fingerprinting: shuffle করা content-কে signature দিয়ে cluster করা।
• Data warehousing: record-কে canonical signature দিয়ে bucket করে aggregate।
• Cryptanalysis: একই letter-frequency profile-এর message গোষ্ঠীবদ্ধ করা।

মূল pattern: প্রতিটা item-কে অপরিবর্তনীয় signature-এ রূপান্তর করো, একই signature এক bucket — তুলনা ছাড়াই, O(n·k)।

---

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