Problem link ও উৎস
- **Original source:** Classic frequency-count exercise
- **Platform:** LeetCode —
- **Topic:** hash map / frequency count
- **Difficulty:** Easy
- **Pattern:** frequency counting
- **Basic idea inherited from:** count arrays ([../../01-math-based-programming-fundamentals/](../../01-math-based-programming-fundamentals/README.md)) — ছোট alphabet-এর count array-র বড় ভাই hash map
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো string `s` আর `t` দেওয়া আছে। বলো — এরা কি একে অপরের **anagram**? অর্থাৎ একটার অক্ষরগুলো নাড়াচাড়া করে কি ঠিক অন্যটা বানানো যায়? মানে দুটোতে **একই অক্ষর একই সংখ্যকবার** থাকতে হবে, শুধু ক্রম আলাদা হতে পারে।
```text
s = "listen", t = "silent" → True (একই অক্ষর, ক্রম আলাদা)
s = "rat", t = "car" → False (অক্ষরই মেলে না)
```
### Input ও output {#8-example-input-and-output}
```text
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 (দুটোই খালি)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো দুই ব্যাগ Scrabble-এর tile। অক্ষরগুলো কোন ক্রমে আছে সেটা ম্যাটার করে না — তুমি শুধু প্রতিটা ব্যাগের প্রতিটা অক্ষর গুনে দুই গণনা মিলিয়ে দেখো। দুই ব্যাগে A কয়টা, B কয়টা... সব মিললে এক ব্যাগ থেকে অন্যটা সাজানো যায়। সেই গোনা-তালিকা দুটোই Counter।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **count array**-র উপর — যেটা math fundamentals-এ ([../../01-math-based-programming-fundamentals/](../../01-math-based-programming-fundamentals/README.md)) তুমি দেখেছ: ছোট, জানা alphabet-এর জন্য 26-ঘরের একটা array-তে count রাখা। Hash map হলো সেই count array-রই unlimited, sparse-index version। [../patterns.md](../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 তুলনা করে দেয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: `s`-এর প্রতিটা অক্ষর `t`-তে খুঁজে বের করে মুছে দাও; সব মুছে ফেলতে পারলে anagram।
```text
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 কি"-তে নেমে আসে।
### ছবিতে বোঝা {#7-visual-explanation}
`s = "listen"`, `t = "silent"`। দুই দিকে count বানাই:
```text
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 হলে:
```text
Counter("rat") = {r:1, a:1, t:1}
Counter("car") = {c:1, a:1, r:1}
't' আছে বাঁয়ে, নেই ডানে; 'c' উল্টোটা → False
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
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`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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`।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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)-এ একই উত্তর দেয়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: count array (math fundamentals-এর counting) — ছোট alphabet হলে 26-ঘরের array, না হলে hash map। [../patterns.md](../patterns.md)-র Pattern 1 আর [../concept.md](../concept.md)-র Counter snippet দেখো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Group Anagrams —