কনটেন্টে যান

003 — Valid Anagram

Problem link ও উৎস

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

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

দুটো string s আর t দেওয়া আছে। বলো — এরা কি একে অপরের anagram? অর্থাৎ একটার অক্ষরগুলো নাড়াচাড়া করে কি ঠিক অন্যটা বানানো যায়? মানে দুটোতে একই অক্ষর একই সংখ্যকবার থাকতে হবে, শুধু ক্রম আলাদা হতে পারে।

উদাহরণ
s = "listen", t = "silent"  →  True   (একই অক্ষর, ক্রম আলাদা)
s = "rat",    t = "car"     →  False  (অক্ষরই মেলে না)

Input ও output

উদাহরণ
Input : s = "anagram", t = "nagaram"   Output: True
Input : s = "rat",     t = "car"       Output: False
Edge  : s = "a",       t = "ab"        Output: False  (length আলাদা)
Edge  : s = "",        t = ""          Output: True   (দুটোই খালি)

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

ভাবো দুই ব্যাগ Scrabble-এর tile। অক্ষরগুলো কোন ক্রমে আছে সেটা ম্যাটার করে না — তুমি শুধু প্রতিটা ব্যাগের প্রতিটা অক্ষর গুনে দুই গণনা মিলিয়ে দেখো। দুই ব্যাগে A কয়টা, B কয়টা... সব মিললে এক ব্যাগ থেকে অন্যটা সাজানো যায়। সেই গোনা-তালিকা দুটোই Counter।

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

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

এটা দাঁড়িয়ে আছে count array-র উপর — যেটা math fundamentals-এ (../../01-math-based-programming-fundamentals/) তুমি দেখেছ: ছোট, জানা alphabet-এর জন্য 26-ঘরের একটা array-তে count রাখা। Hash map হলো সেই count array-রই unlimited, sparse-index version। ../patterns.md-এ এটা Pattern 1 — frequency counting।

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

লুকানো logic: দুটো string anagram তখনই যখন তাদের count profile হুবহু সমান — অর্থাৎ প্রতিটা অক্ষর দুই দিকে সমান সংখ্যকবার আছে। ক্রম গুরুত্বহীন; শুধু "কোন অক্ষর কয়টা" সেই multiset-টাই সব। সাথে একটা ছোট্ট গণিত: length আলাদা হলে কখনোই anagram হতে পারে না।

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

একটা frequency map — Python-এ collections.Counter (ভেতরে dict)। প্রতিটা অক্ষরকে তার গণনার সাথে map করে: char → count।

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

Counter এক pass-এ পুরো count profile বানায়, O(1) average insert/update দিয়ে। তারপর দুটো Counter-এর সমতা যাচাই করা সহজ — Counter(s) == Counter(t)। অক্ষরে অক্ষরে তুলনা করার দরকার নেই; structure নিজেই profile তুলনা করে দেয়।

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

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

প্রথম সরল চিন্তা: s-এর প্রতিটা অক্ষর t-তে খুঁজে বের করে মুছে দাও; সব মুছে ফেলতে পারলে anagram।

উদাহরণ
length আলাদা হলে → False
t-কে list বানাও
s-এর প্রতিটা ch: t-তে ch খুঁজে remove করো; না পেলে → False
সব মুছে গেলে → True

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

t-তে প্রতিটা অক্ষর খুঁজতে list scan = O(n), আর সেটা s-এর প্রতিটা অক্ষরের জন্য = মোট O(n^2)। আরেকটা সরল উপায় হলো দুটো string sort করে তুলনা — O(n log n)। কিন্তু আমরা জানি গোনাই যথেষ্ট, আর গোনা O(n)-এ হয়, তাই sort-ও বাড়তি খরচ।

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

মূল observation: anagram = সমান count profile। অক্ষর কোথায় আছে তা ভুলে যাও; শুধু কোনটা কয়টা সেটা গোনো। দুই গণনা সমান হলেই উত্তর হ্যাঁ।

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

দুই string-এর জন্য char → count map বানাও (এক pass করে), তারপর map দুটো সমান কি না দেখো। সমান মানে প্রতিটা অক্ষর দুই দিকে সমানবার — anagram। তার আগে length মিলিয়ে নিলে অনেক case সঙ্গে সঙ্গে বাদ পড়ে।

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

মোচড়: অক্ষরগুলোকে একে অপরের সাথে মেলানো বন্ধ করো; তাদের count profile তুলনা করো। "সাজানো যায় কি" প্রশ্নটা "একই multiset কি"-তে নেমে আসে।

ছবিতে বোঝা

s = "listen", t = "silent"। দুই দিকে count বানাই:

উদাহরণ
Counter("listen") = {l:1, i:1, s:1, t:1, e:1, n:1}
Counter("silent") = {s:1, i:1, l:1, e:1, n:1, t:1}

profile তুলনা (ক্রম নয়):  সব অক্ষরের count সমান  →  True

আর mismatch হলে:

উদাহরণ
Counter("rat") = {r:1, a:1, t:1}
Counter("car") = {c:1, a:1, r:1}
't' আছে বাঁয়ে, নেই ডানে; 'c' উল্টোটা  →  False

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

Input s = "rat", t = "car":

  1. length: 3 == 3 → এগোও।
  2. Counter("rat") = {r:1, a:1, t:1}।
  3. Counter("car") = {c:1, a:1, r:1}।
  4. সমতা যাচাই: বাঁয়ে t আছে, ডানে নেই; ডানে c আছে, বাঁয়ে নেই → অসমান।
  5. return False।

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

Python

Python
from collections import Counter

def is_anagram(s, t):
    if len(s) != len(t):            # length আলাদা হলে কখনোই anagram নয়
        return False
    return Counter(s) == Counter(t) # count profile তুলনা

# ---- tests ----
assert is_anagram("anagram", "nagaram") == True
assert is_anagram("rat", "car") == False
assert is_anagram("a", "ab") == False        # length আলাদা
assert is_anagram("", "") == True            # দুটোই খালি
print("সব test pass!")

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

  • from collections import Counter — char → count map এক লাইনে বানানোর tool।
  • if len(s) != len(t): return False — দ্রুত বাতিল; আলাদা দৈর্ঘ্যে anagram অসম্ভব, আর এতে কাজও বাঁচে।
  • Counter(s) == Counter(t) — দুই string-এর count profile বানিয়ে সমতা যাচাই; সমান হলে True।

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

"anagram" ও "nagaram" — দুটোই {a:3, n:1, g:1, r:1, m:1}, সমান → True। "rat" ও "car"-এ profile আলাদা → False। "a" ও "ab" length-এই আটকে যায় → False। দুই খালি string-এর Counter দুটোই খালি, সমান → True। শেষে print: সব test pass!।

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

সময়

O(n) — প্রতিটা অক্ষর একবার করে গোনা হয়; Counter তুলনাও distinct অক্ষরের সংখ্যায় linear।

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

O(k) — k = distinct অক্ষরের সংখ্যা (lowercase English হলে বড়জোর 26, অর্থাৎ কার্যত O(1))।

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

  • length check বাদ দেওয়া — যদিও Counter সমতা এমনিতেও ঠিক ধরবে, length আগে মিলিয়ে নিলে অনেক case দ্রুত বাদ পড়ে।
  • case/space নিয়ে অনুমান — "Listen" বনাম "silent" তখনই anagram যদি আগে normalize (lowercase, space বাদ) করো; problem-এর শর্ত আগে পড়ো।
  • দুই string sort করে তুলনা করা — কাজ করে, কিন্তু O(n log n); গোনা O(n)-এ একই উত্তর দেয়।

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

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

ভিত্তি: count array (math fundamentals-এর counting) — ছোট alphabet হলে 26-ঘরের array, না হলে hash map। ../patterns.md-র Pattern 1 আর ../concept.md-র Counter snippet দেখো।

পরের অনুশীলন

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

Frequency counting: raw item তুলনা না করে value → count profile তুলনা করো — anagram, "same letters", "how many times"-এর মূল চাল।

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

ভবিষ্যতের আমাকে: "একই অক্ষর / anagram / নাড়াচাড়া করে বানানো" শুনলেই Counter। ক্রম ভুলে যাও, count মেলাও; আর length আগে মিলিয়ে নিয়ে কাজ বাঁচাও। এটাই Ransom Note ও Group Anagrams-এর সিঁড়ির প্রথম ধাপ।

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