003 — Valid Anagram¶

Source¶

Original source: Classic frequency-counting exercise
Platform: LeetCode — https://leetcode.com/problems/valid-anagram/
Topic: string / hash map
Difficulty: Easy
Pattern: frequency counting (count map সমান কিনা)
Basic idea inherited from: Math fundamentals-এর counting — arrangement না, occurrence count মেলানো

1. Problem in simple words¶

দুটো string s আর t দেওয়া আছে। বলো ওরা একে অপরের anagram কিনা — মানে ঠিক একই অক্ষরগুলো ঠিক একই সংখ্যকবার ব্যবহার করে কিনা, শুধু সাজানোটা আলাদা। যেমন "listen" আর "silent" anagram; "rat" আর "car" নয়।

"anagram" vs "nagaram"  -> True  (একই অক্ষর, একই count)
"rat"     vs "car"      -> False (r vs c আলাদা)

2. Which basic idea does this inherit from?¶

ভিত হলো counting — math fundamentals-এর গণনা। anagram কিনা সেটা সাজানোর (arrangement, n! রকম) উপর নির্ভর করে না; নির্ভর করে প্রতিটা অক্ষর কতবার এল তার উপর। তাই দুটো string-এর "অক্ষর-গণনার সারাংশ" মিললেই anagram। গভীরে: ../../01-math-based-programming-fundamentals/03-counting-combinatorics/।

3. What is the hidden math or logic?¶

লুকানো logic: দুটো string anagram তখনই এবং কেবল তখনই (iff) যখন তাদের character-count map সমান। n! রকম সাজানো পরীক্ষা না করে শুধু count compare করি — কারণ count একই হলে একটাকে অন্যটায় rearrange করা সম্ভব। প্রথম shortcut: length আলাদা হলে কখনোই anagram নয়।

4. Which data structure is needed?¶

একটা hash map (dict) — প্রতিটা character → কতবার এল। (lowercase letter হলে 26-ঘরের একটা array আরো সস্তা counter, patterns.md যেমন বলেছে।)

5. Why this data structure fits¶

প্রতিটা অক্ষরের count বাড়ানো/কমানো আর তুলনা — সবই dict-এ average O(1)। array-তে "এই অক্ষর কতবার" বারবার খুঁজলে O(n) করে লাগত; dict সেটাকে এক pass-এ O(n) মোটে নামিয়ে আনে।

6. Real-life analogy¶

দুই থলে Scrabble টাইল ভাবো। ওরা একই কিনা জানতে টাইলগুলো সাজিয়ে শব্দ বানানোর দরকার নেই — শুধু প্রতিটা থলেতে কয়টা 'a', কয়টা 'b' ... গুনে মিলিয়ে দেখো। সব গোনা মিললে থলে দুটো আসলে একই।

7. Visual explanation¶

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

count শুরুতে {}:

s "rat" গুনি:  r:1, a:1, t:1   -> {r:1, a:1, t:1}

t "car" বিয়োগ করি:
  c -> count-এ 'c' নেই! -> False সাথে সাথে

(মিললে শেষে সব count 0 হয়ে dict খালি হতো)

8. Example input and output¶

Input : s = "anagram", t = "nagaram" -> Output: True
Input : s = "rat",     t = "car"     -> Output: False

Edge case (length আলাদা): s = "a", t = "ab" -> False

9. Brute force thinking¶

প্রথম সরল চিন্তা: দুটো string sort করো, তারপর সমান কিনা দেখো — anagram হলে sort করলে একদম এক হবে।

sorted("anagram") == sorted("nagaram")  ->  "aaagmnr" == "aaagmnr"  -> True

10. Why brute force is slow¶

sort করা O(n log n) — count করার O(n)-এর চেয়ে ধীর। sort কাজ করে ঠিকই, কিন্তু আসলে দরকার শুধু গোনা; পুরো order বানানো বাড়তি খরচ। (তবে sort version মনে রাখা ভালো — group anagrams, tracker #17-এ এই "canonical key" idea লাগবে।)

11. Key observation¶

মূল observation: anagram মানে একই multiset of characters — অর্থাৎ একই count map। সাজানো অপ্রাসঙ্গিক, তাই সাজানো বানানোও অপ্রয়োজনীয়; শুধু গুনে তুলনা করো।

12. Optimized intuition¶

s-এর প্রতিটা অক্ষরের জন্য count +1 করো। তারপর t-এর প্রতিটা অক্ষরের জন্য count -1 করো; কোনো অক্ষর না থাকলে → not anagram। শেষে সব count 0 হলে (dict খালি) anagram। length আগে মিলিয়ে নিলে অর্ধেক কাজ বাঁচে।

13. Thinking tweak¶

মোচড়: "একটাকে আরেকটায় সাজানো যায় কিনা" ভাবার বদলে ভাবো "দুটোর অক্ষর-গণনা হুবহু এক কিনা।" তখন n! সাজানো গায়েব হয়ে একটা O(n) count-compare-এ নেমে আসে।

14. Step-by-step dry run¶

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

length সমান (3 == 3), এগোও।
s গুনি: r→1, a→1, t→1 → count = {r:1, a:1, t:1}।
t বিয়োগ: প্রথম অক্ষর c → count-এ c নেই → সাথে সাথে False।

15. Python solution¶

def is_anagram(s, t):
    if len(s) != len(t):           # length আলাদা হলে কখনোই না
        return False
    count = {}
    for ch in s:                   # s-এর অক্ষর গুনি
        count[ch] = count.get(ch, 0) + 1
    for ch in t:                   # t দিয়ে বিয়োগ করি
        if ch not in count:
            return False
        count[ch] -= 1
        if count[ch] == 0:
            del count[ch]
    return len(count) == 0         # সব মিলে গেলে dict খালি

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

16. Line-by-line code explanation¶

if len(s) != len(t): return False — দ্রুত shortcut; আলাদা length মানে কখনোই anagram নয়।
count.get(ch, 0) + 1 — অক্ষরটা প্রথমবার হলে 0 ধরে, তারপর +1।
if ch not in count: return False — t-তে এমন অক্ষর যেটা s-এ নেই → না।
count[ch] -= 1 ... del count[ch] — মিলে গেলে ঘরটা সরিয়ে ফেলি; সব মিললে dict খালি হবে।
return len(count) == 0 — খালি dict মানে প্রতিটা count exact মিলেছে।

17. Output walkthrough¶

"anagram"/"nagaram": length সমান, s গোনার পর t বিয়োগ করতে করতে সব count 0 → dict খালি → True। "rat"/"car": c না পেয়ে সাথে সাথে False। "a"/"ab": length আলাদা → False। শেষে print: সব test pass!।

18. Time complexity¶

O(n) — দুটো string একবার করে scan; প্রতিটা dict operation O(1)।

19. Space complexity¶

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

20. Common mistakes¶

length আগে না মেলানো — তাও ঠিক উত্তর আসে, কিন্তু shortcut হারাও।
শুধু একদিকে গোনা (s বাড়িয়ে t বিয়োগ না করা) — তখন count compare ভুল হয়।
case/space সংবেদনশীলতা ভুলে যাওয়া — দরকার হলে আগে normalize (lowercase) করো।

21. Which basic problem this inherits from¶

ভিত্তি: counting/frequency map (Two Sum-এর hash-map idea-র জ্ঞাতি)। এই count-compare-ই group anagrams (#17)-এ canonical key হিসেবে ফিরে আসে। chapter-এর ../patterns.md-এর "Pattern 5 — Frequency Counting" দেখো।

22. Similar harder problems¶

Group Anagrams (count/sort-কে bucket key বানাও) — https://leetcode.com/problems/group-anagrams/ (#17)
Find All Anagrams in a String (sliding window + count) — https://leetcode.com/problems/find-all-anagrams-in-a-string/
Top K Frequent Elements — https://leetcode.com/problems/top-k-frequent-elements/

23. Pattern learned¶

Frequency counting: arrangement না, count map compare করো — anagram/permutation/unique-গোছের প্রশ্নের এক-pass O(n) চাবি।

24. Final summary¶

ভবিষ্যতের আমাকে: "anagram = একই count map।" "anagram/permutation of each other" শুনলেই sort না করে count map মেলাও — O(n), length-check shortcut সহ।

25. JavaScript solution (with test cases)¶

frequency counting — length আগে মেলাও, তারপর s গুনে t দিয়ে বিয়োগ; কোথাও negative/missing হলেই না।

// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function isAnagram(s, t) {
  if (s.length !== t.length) return false;       // length আলাদা → কখনোই না
  const count = new Map();
  for (const ch of s) count.set(ch, (count.get(ch) || 0) + 1);
  for (const ch of t) {
    const c = count.get(ch) || 0;
    if (c === 0) return false;                    // t-তে এমন অক্ষর যা s-এ নেই/ফুরিয়েছে
    count.set(ch, c - 1);
  }
  return true;                                    // সব মিলে গেছে
}

// ---- test cases (file-এর example + edge case) ----
assert(isAnagram("anagram", "nagaram") === true, "anagram");
assert(isAnagram("rat", "car") === false, "rat/car");
assert(isAnagram("a", "ab") === false, "length আলাদা");
assert(isAnagram("", "") === true, "দুই খালি");
assert(isAnagram("aabb", "bbaa") === true, "repeated");
console.log("সব JS test pass!");

JS টীকা: char count রাখতে Map (Unicode/যেকোনো অক্ষরে নিরাপদ); শুধু lowercase a–z হলে 26-ঘরের Array(26).fill(0) আরও সস্তা। count.get(ch) || 0 দিয়ে missing key 0 ধরো — Python dict.get(ch, 0)-এর বদলি। length-check shortcut আগে রাখলে অর্ধেক কাজ বাঁচে।

26. TypeScript solution (with test cases)¶

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const count = new Map<string, number>();
  for (const ch of s) count.set(ch, (count.get(ch) ?? 0) + 1);
  for (const ch of t) {
    const c = count.get(ch) ?? 0;
    if (c === 0) return false;
    count.set(ch, c - 1);
  }
  return true;
}

function expect(actual: boolean, expected: boolean, msg = ""): void {
  if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}

const cases: ReadonlyArray<readonly [string, string, boolean]> = [
  ["anagram", "nagaram", true], ["rat", "car", false],
  ["a", "ab", false], ["", "", true], ["aabb", "bbaa", true],
];
for (const [s, t, want] of cases) expect(isAnagram(s, t), want, `${s}/${t}`);
console.log("সব TS test pass!");

TS টীকা: Map<string, number> key=char, value=count স্পষ্ট করে; ?? 0 (nullish) দিয়ে missing key নিরাপদে 0, আর return boolean থাকায় caller ভুল ধরতে পারে না।

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

Anagram/permutation check: শব্দখেলা, spell-related feature, "একই অক্ষর ভিন্ন সাজানো" শনাক্ত।
Duplicate/grouping by signature: sorted-char বা count map কে canonical key বানিয়ে group anagrams (একই বালতিতে ফেলা)।
Multiset equality: দুই collection-এ একই উপাদান একই সংখ্যায় কিনা (inventory, bag-of-words মেলানো)।
Sliding-window anagram search: বড় string-এ কোনো pattern-এর সব anagram খোঁজা (count map + window)। মূল pattern — "arrangement নয়, occurrence count মেলানো (O(n) frequency map)" — anagram, permutation, bag-of-words, histogram-তুলনা জুড়ে বড় ছবিতে ফেরে।

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