Problem link ও উৎস
- **Original source:** Classic frequency-counting exercise
- **Platform:** LeetCode —
- **Topic:** string / hash map
- **Difficulty:** Easy
- **Pattern:** frequency counting (count map সমান কিনা)
- **Basic idea inherited from:** Math fundamentals-এর counting — arrangement না, occurrence count মেলানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো string `s` আর `t` দেওয়া আছে। বলো ওরা একে অপরের **anagram** কিনা — মানে ঠিক একই অক্ষরগুলো ঠিক একই সংখ্যকবার ব্যবহার করে কিনা, শুধু সাজানোটা আলাদা। যেমন `"listen"` আর `"silent"` anagram; `"rat"` আর `"car"` নয়।
```text
"anagram" vs "nagaram" -> True (একই অক্ষর, একই count)
"rat" vs "car" -> False (r vs c আলাদা)
```
### Input ও output {#8-example-input-and-output}
```text
Input : s = "anagram", t = "nagaram" -> Output: True
Input : s = "rat", t = "car" -> Output: False
Edge case (length আলাদা): s = "a", t = "ab" -> False
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
দুই থলে Scrabble টাইল ভাবো। ওরা একই কিনা জানতে টাইলগুলো সাজিয়ে শব্দ বানানোর দরকার নেই — শুধু প্রতিটা থলেতে কয়টা 'a', কয়টা 'b' ... গুনে মিলিয়ে দেখো। সব গোনা মিললে থলে দুটো আসলে একই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত হলো **counting** — math fundamentals-এর গণনা। anagram কিনা সেটা সাজানোর (arrangement, n! রকম) উপর নির্ভর করে না; নির্ভর করে প্রতিটা অক্ষর কতবার এল তার উপর। তাই দুটো string-এর "অক্ষর-গণনার সারাংশ" মিললেই anagram। গভীরে: [../../01-math-based-programming-fundamentals/03-counting-combinatorics/](../../01-math-based-programming-fundamentals/03-counting-combinatorics/README.md)।
### ভেতরের যুক্তি {#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) মোটে নামিয়ে আনে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: দুটো string sort করো, তারপর সমান কিনা দেখো — anagram হলে sort করলে একদম এক হবে।
```text
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-এ নেমে আসে।
### ছবিতে বোঝা {#7-visual-explanation}
`s = "rat"`, `t = "car"`:
```text
count শুরুতে {}:
s "rat" গুনি: r:1, a:1, t:1 -> {r:1, a:1, t:1}
t "car" বিয়োগ করি:
c -> count-এ 'c' নেই! -> False সাথে সাথে
(মিললে শেষে সব count 0 হয়ে dict খালি হতো)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `s = "rat"`, `t = "car"`:
1. length সমান (3 == 3), এগোও।
2. `s` গুনি: `r→1`, `a→1`, `t→1` → `count = {r:1, a:1, t:1}`।
3. `t` বিয়োগ: প্রথম অক্ষর `c` → `count`-এ `c` নেই → সাথে সাথে `False`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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 মিলেছে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`"anagram"/"nagaram"`: length সমান, s গোনার পর t বিয়োগ করতে করতে সব count 0 → dict খালি → `True`। `"rat"/"car"`: `c` না পেয়ে সাথে সাথে `False`। `"a"/"ab"`: length আলাদা → `False`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
frequency counting — length আগে মেলাও, তারপর `s` গুনে `t` দিয়ে বিয়োগ; কোথাও negative/missing হলেই না।
```javascript
// 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 আগে রাখলে অর্ধেক কাজ বাঁচে।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) return false;
const count = new Map