017 — Group Anagrams¶

Source¶

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 বানানো

1. Problem in simple words¶

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

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
দল   : ["eat","tea","ate"], ["tan","nat"], ["bat"]

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

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-জোড়া তুলনা ছাড়াই।

6. Real-life analogy¶

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

7. Visual explanation¶

["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{ ..., K2:[tan,nat] }
"bat" -> a:1,b:1,t:1        (key K3) -> নতুন bucket [bat]

ফল: [[eat,tea,ate], [tan,nat], [bat]]

8. Example input and 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"]]

9. Brute force thinking¶

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

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-এ নেমে আসে।

14. Step-by-step dry run¶

Input ["eat", "ate", "bat"]:

"eat": count → a:1,e:1,t:1; key (...,1,...,1,...,1,...); dict খালি → নতুন bucket; groups = {K_eat: ["eat"]}।
"ate": count → a:1,e:1,t:1; key একই K_eat; bucket-এ append → {K_eat: ["eat","ate"]}।
"bat": count → a:1,b:1,t:1; key নতুন K_bat; নতুন bucket → {K_eat:["eat","ate"], K_bat:["bat"]}।
list(groups.values()) → [["eat","ate"], ["bat"]]।

15. Python solution¶

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।

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

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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 ব্যবহার করো।

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

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/

23. Pattern learned¶

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

24. Final summary¶

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

25. JavaScript solution (with test cases)¶

প্রতিটা word-এর 26-count signature-কে string key বানিয়ে Map-এ bucket।

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-এর ক্রম স্থির।

26. TypeScript solution (with test cases)¶

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-এ আটকায়।

27. কোথায় কাজে লাগে (real-world use)¶

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।