কনটেন্টে যান

010 — Group Anagrams

Problem link ও উৎস

  • 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 মানে একই দল

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

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

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

উদাহরণ
["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"]]   (দলের ক্রম যেকোনো)

Input : [""]            Output: [[""]]
Input : ["a"]           Output: [["a"]]
Input : ["abc","bca","cab","xyz"]
Output: [["abc","bca","cab"], ["xyz"]]

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

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

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

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

এটা দাঁড়িয়ে frequency counting-এর উপর (Valid Anagram, #3)। সেখানে শিখেছ দুটো string anagram কি না বোঝা যায় তাদের অক্ষরের count profile মিলিয়ে। এখানে সেই profile-কেই key বানাচ্ছি: একই profile-ওয়ালা সব string এক bucket-এ। ../patterns.md-তে এটাই Pattern 3 — grouping by canonical key।

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

লুকানো logic: anagram একটা equivalence relation — "একই অক্ষরসেট" দিয়ে সব string কে শ্রেণিতে ভাগ করা যায়। প্রতিটা শ্রেণির জন্য একটা canonical form (একটাই প্রতিনিধি রূপ) বেছে নিলে, একই শ্রেণির সব সদস্য সেই একই রূপে এসে দাঁড়ায়। দুটো সরল canonical রূপ: (ক) অক্ষরগুলো sort করা string, বা (খ) 26টা অক্ষরের count-এর tuple।

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

একটা hash map, যেখানে key = canonical form আর value = সেই form-এ পড়া word-দের list। Python-এ collections.defaultdict(list) ব্যবহার করলে নতুন key-তে list নিজে থেকেই তৈরি হয়ে যায়, তাই "key আছে কি না" আগে check করতে হয় না।

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

আমরা চাই "একই key-ওয়ালা জিনিসগুলো একসাথে জমা হোক" — hash map ঠিক এই কাজটাই গড়ে O(1)-এ করে। প্রতিটা word-এর key হিসেব করে সরাসরি তার bucket-এ append করি; word-গুলোকে জোড়ায় জোড়ায় মিলিয়ে দেখার দরকার নেই। List হলে দল খুঁজতে প্রতিবার scan করতে হতো — O(n^2)।

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

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

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

উদাহরণ
প্রতিটা word w-র জন্য (যদি আগে দলভুক্ত না হয়):
    নতুন দল শুরু করো
    বাকি প্রতিটা word u-র জন্য:
        w আর u anagram হলে দলে যোগ করো

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

প্রতিটা word-কে বাকি সবার সাথে মেলানো মানে O(n^2) জোড়া তুলনা, আর প্রতিটা তুলনায় আবার অক্ষর গোনা/sort করার খরচ। আসল অপচয়: আমরা একই word বারবার পরীক্ষা করছি, যদিও প্রতিটা word-এর "পরিচয়" (canonical key) একবার হিসেব করলেই সব ঠিক জায়গায় বসে যেত।

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

মূল observation: একই দলের সব সদস্য একটাই canonical key-তে নেমে আসে। তাই দল বানানোর জন্য word-দের পরস্পরের সাথে তুলনা করার দরকার নেই — প্রতিটা word একবার normalize করো, hash map নিজেই সমান key-ওয়ালাদের একসাথে জড়ো করবে।

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

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

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

মোচড়: জিনিস দুটোকে তুলনা কোরো না — প্রত্যেককে একটা সাধারণ রূপে অনুবাদ করো, hash map-কে দল বানাতে দাও। এই tweak O(n^2) pairwise comparison-কে O(n) bucketing-এ নামিয়ে আনে। "group", "bucket", "which are equivalent" শুনলেই এই চাল মনে পড়া চাই।

ছবিতে বোঝা

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

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

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

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

Python

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

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

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

Output মিলিয়ে দেখা

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

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

সময়

O(n · k log k) — n হলো word সংখ্যা, k হলো গড় দৈর্ঘ্য; প্রতিটা word-এ sort O(k log k)। count-tuple key ব্যবহার করলে নামে O(n · k)।

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

O(n · k) — সব word আর তাদের key hash map-এ জমা থাকে।

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

  • canonical key অসংগত বানানো — একটা word sort করা আর আরেকটা না করা; সব word-এ একই rule খাটাতে হবে।
  • sorted(w)-এর ফল list, সেটাকে "".join(...) না করে সরাসরি key বানানো — list hashable নয়, তাই dict key হতে পারবে না (string বা tuple লাগবে)।
  • দলের ভেতরের ক্রম নিয়ে assert লেখা — insertion order-নির্ভর; test স্থিতিশীল রাখতে দল sort করে মেলাও।

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

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

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

পরের অনুশীলন

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

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

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

ভবিষ্যতের আমাকে: "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।