Skip to content

010 — Group Anagrams

Source

  • Original source: Classic canonical-key grouping exercise
  • Platform: LeetCode — https://leetcode.com/problems/group-anagrams/
  • Topic: hash map (grouping)
  • Difficulty: Medium
  • Pattern: grouping by canonical key
  • Basic idea inherited from: frequency counting — একই count profile মানে একই দল

1. Problem in simple words

একগুচ্ছ string words দেওয়া আছে। যেসব string একে অপরের anagram (অর্থাৎ ঠিক একই অক্ষর, শুধু সাজানো আলাদা), তাদের একই দলে জড়ো করতে হবে। ফেরত দিতে হবে দলগুলোর একটা list; দলগুলোর ক্রম যেকোনো হতে পারে।

["eat", "tea", "tan", "ate", "nat", "bat"]
→ [["eat","tea","ate"], ["tan","nat"], ["bat"]]

2. Which basic idea does this inherit from?

এটা দাঁড়িয়ে frequency counting-এর উপর (Valid Anagram, #3)। সেখানে শিখেছ দুটো string anagram কি না বোঝা যায় তাদের অক্ষরের count profile মিলিয়ে। এখানে সেই profile-কেই key বানাচ্ছি: একই profile-ওয়ালা সব string এক bucket-এ। ../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)।

6. Real-life analogy

ভাবো ডাকঘরে অনেক চিঠি এসেছে, প্রতিটায় এলাকার pin code লেখা। তুমি চিঠিগুলো একে অপরের সাথে মিলিয়ে দেখো না — শুধু pin code পড়ে সেই code-এর বাক্সে ফেলে দাও। এক রাউন্ডেই সব চিঠি নিজ নিজ এলাকায় ভাগ হয়ে যায়। এখানে pin code-ই canonical key, আর বাক্সগুলো hash map-এর bucket।

7. Visual explanation

key = sorted অক্ষর। প্রতিটা word তার key-র bucket-এ পড়ছে:

"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-ই উত্তর।

8. Example input and output

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

9. Brute force thinking

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

প্রতিটা 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" শুনলেই এই চাল মনে পড়া চাই।

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

15. Python solution

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 স্থিতিশীল থাকে)।

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

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 করে মেলাও।

21. Which basic problem this inherits from

ভিত্তি: Valid Anagram (#3)-এর frequency/count profile। সেখানে দুটো string-এর profile মেলানো হয়; এখানে সেই profile-কে key বানিয়ে n-টা string একসাথে দলবদ্ধ করা হয়। পুরো চাল ../patterns.md-র Pattern 3-এ।

22. Similar harder problems

23. Pattern learned

Grouping by canonical key: প্রতিটা item-কে একটা প্রতিনিধি রূপে অনুবাদ করো, তারপর defaultdict(list)-কে সমান-key জিনিসগুলো একসাথে জড়ো করতে দাও — O(n^2) pairwise তুলনা ছাড়াই।

24. Final summary

ভবিষ্যতের আমাকে: "group", "bucket", "which are equivalent" শুনলেই হাত যাবে canonical key-র দিকে। আসল প্রশ্ন একটাই — কোন রূপে আনলে equivalent জিনিসগুলো ইচ্ছে করে collide করবে? এই note-টা interview-র তিনটা showcase-এর একটা; key design চোখ বন্ধ করে বলতে পারা চাই।

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