003 — Valid Anagram¶

Source¶

Original source: Classic frequency-count exercise
Platform: LeetCode — https://leetcode.com/problems/valid-anagram/
Topic: hash map / frequency count
Difficulty: Easy
Pattern: frequency counting
Basic idea inherited from: count arrays (../../01-math-based-programming-fundamentals/) — ছোট alphabet-এর count array-র বড় ভাই hash map

1. Problem in simple words¶

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

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

2. Which basic idea does this inherit from?¶

এটা দাঁড়িয়ে আছে 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।

3. What is the hidden math or logic?¶

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

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

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

8. Example input and 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   (দুটোই খালি)

9. Brute force thinking¶

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

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

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

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

15. Python solution¶

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

16. Line-by-line code explanation¶

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

17. Output walkthrough¶

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

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

Group Anagrams — https://leetcode.com/problems/group-anagrams/ (এই tracker-এর #10; anagram-দের একসাথে group করা)
Find All Anagrams in a String — https://leetcode.com/problems/find-all-anagrams-in-a-string/ (sliding window-এ count মেলানো)
Ransom Note — https://leetcode.com/problems/ransom-note/ (#4; সমান নয়, "cover করতে পারে কি")

23. Pattern learned¶

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

24. Final summary¶

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

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