Problem link ও উৎস
- **Original source:** Classic frequency-count exercise
- **Platform:** LeetCode —
- **Topic:** hash map / frequency count
- **Difficulty:** Easy
- **Pattern:** frequency counting
- **Basic idea inherited from:** Valid Anagram — তবে "সমান" নয়, "cover করতে পারে কি না" (count coverage)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো string দেওয়া আছে — `ransomNote` আর `magazine`। তুমি `magazine`-এর অক্ষর কেটে কেটে `ransomNote` বানাতে চাও। শর্ত: `magazine`-এর প্রতিটা অক্ষর **একবারই** ব্যবহার করা যাবে। বলো — `ransomNote`-টা কি বানানো **সম্ভব**?
```text
ransomNote = "aa", magazine = "aab" → True (দুটো 'a' আছে, লাগবে দুটো)
ransomNote = "aa", magazine = "ab" → False (একটাই 'a', কিন্তু লাগে দুটো)
```
### Input ও output {#8-example-input-and-output}
```text
Input : ransomNote = "a", magazine = "b" Output: False
Input : ransomNote = "aa", magazine = "ab" Output: False
Input : ransomNote = "aa", magazine = "aab" Output: True
Edge : ransomNote = "", magazine = "abc" Output: True (কিছুই লাগে না)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি রান্না করতে বসেছ আর recipe-তে লাগবে 2টা ডিম, 1 কাপ চিনি। তুমি ফ্রিজ আর প্যান্ট্রির stock গোনো, তারপর প্রতিটা উপকরণে দেখো "যথেষ্ট আছে তো?" একটাও কম পড়লে recipe হবে না। Recipe = ransomNote, প্যান্ট্রি = magazine, গোনা-তালিকা = Counter।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **Valid Anagram** (#3)-এর উপর দাঁড়ানো — কিন্তু একটা গুরুত্বপূর্ণ পার্থক্য। Anagram চায় দুই count profile **সমান**; Ransom Note চায় magazine-এর count যেন note-এর count **cover** করে (প্রতিটা অক্ষরে magazine ≥ note)। এটা সমতা নয়, এক-দিকের যথেষ্টতা। [../patterns.md](../patterns.md)-এ এটাও Pattern 1 — *frequency counting*।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **per-character inequality**: প্রতিটা অক্ষর `ch`-এর জন্য দরকার `count_magazine[ch] >= count_note[ch]`। সব অক্ষরে এটা সত্যি হলে note বানানো যায়। একটা অক্ষরেও magazine কম পড়লে — অসম্ভব। অর্থাৎ "subset of a multiset" — note-এর multiset কি magazine-এর multiset-এর ভেতরে আঁটে?
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **frequency map** — `collections.Counter`। আমরা magazine-এর প্রতিটা অক্ষরের stock গুনি, তারপর note-এর প্রতিটা চাহিদার সাথে মিলিয়ে দেখি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Counter দিয়ে magazine-এর stock এক pass-এ বানানো যায়, আর note-এর প্রতিটা চাহিদা O(1)-এ যাচাই করা যায় (`mag_counts[ch]` — missing key হলেও 0, কোনো KeyError নেই)। চাহিদা-বনাম-stock এই মেলানোটাই Counter-এর জন্য একদম স্বাভাবিক কাজ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: note-এর প্রতিটা অক্ষর magazine-এর একটা list-এ খুঁজে বের করে মুছে দাও (যাতে দুবার ব্যবহার না হয়); কখনো না পেলে অসম্ভব।
```text
mag_list = list(magazine)
note-এর প্রতিটা ch:
ch যদি mag_list-এ থাকে → remove করো
না থাকলে → return False
return True
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
`mag_list`-এ প্রতিটা অক্ষর খুঁজে remove করা O(n), আর note-এর প্রতিটা অক্ষরের জন্য সেটা = মোট **O(n*m)**। অথচ একবার করে দুই দিক গুনে নিলেই (O(n+m)) সব চাহিদা এক ঝলকে মেলানো যায় — বারবার খোঁজা-মোছাটাই অপচয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **per-character-এ magazine-এর stock note-এর চাহিদা মেটাতে পারলেই হলো** — অক্ষর কোথায় আছে তা বিবেচ্য নয়, শুধু কোনটা কয়টা। তাই দুই গণনা মিলিয়ে দেখাই যথেষ্ট।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
magazine-এর `char → count` map বানাও। তারপর note-এর `char → count` map-এর প্রতিটা entry-তে দেখো magazine-এ ততগুলো (বা বেশি) আছে কি না। একটা অক্ষরেও কম পড়লে `False`; সব মিটলে `True`। সব O(n+m)-এ।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** Valid Anagram-এর `==`-কে বদলে দাও `>=`-তে (per character)। প্রশ্নটা "ঠিক একই অক্ষর কি" থেকে সরে গিয়ে "যথেষ্ট অক্ষর কি আছে" হয়ে যায় — একই গোনা, শুধু তুলনাটা এক-দিকের।
### ছবিতে বোঝা {#7-visual-explanation}
`ransomNote = "aa"`, `magazine = "aab"`। দুই দিকে count বানাই, তারপর চাহিদা মেলাই:
```text
note count = {a:2}
mag count = {a:2, b:1}
চাহিদা 'a': দরকার 2, stock 2 → 2 >= 2 ঠিক আছে
আর কোনো চাহিদা নেই → return True
```
আর কম পড়লে:
```text
note "aa" = {a:2}, mag "ab" = {a:1, b:1}
চাহিদা 'a': দরকার 2, stock 1 → 1 < 2 → return False
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `ransomNote = "aa"`, `magazine = "ab"`:
1. `mag_counts = Counter("ab")` = `{a:1, b:1}`।
2. `note_counts = Counter("aa")` = `{a:2}`।
3. চাহিদা `a`: দরকার 2, `mag_counts['a'] = 1` → `1 < 2` → return `False`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import Counter
def can_construct(ransom_note, magazine):
mag_counts = Counter(magazine) # magazine-এর stock
note_counts = Counter(ransom_note) # note-এর চাহিদা
for ch, need in note_counts.items():
if mag_counts[ch] < need: # stock কম পড়লে অসম্ভব
return False
return True
# ---- tests ----
assert can_construct("a", "b") == False
assert can_construct("aa", "ab") == False
assert can_construct("aa", "aab") == True
assert can_construct("", "anything") == True # কিছুই লাগে না
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `mag_counts = Counter(magazine)` — magazine-এ প্রতিটা অক্ষর কয়টা আছে, তার stock।
- `note_counts = Counter(ransom_note)` — note বানাতে প্রতিটা অক্ষর কয়টা লাগবে, তার চাহিদা।
- `for ch, need in note_counts.items()` — শুধু note-এ থাকা অক্ষরগুলো নিয়েই ভাবলে চলে।
- `if mag_counts[ch] < need` — magazine-এ stock কম? (`Counter`-এ missing key 0 দেয়, তাই KeyError নেই)।
- `return False` — একটা অক্ষরেও কম পড়লে note অসম্ভব।
- `return True` — সব চাহিদা মিটলে note বানানো যায়।
> এক-লাইনের elegant বিকল্প: `not (Counter(ransom_note) - Counter(magazine))` — Counter subtraction শুধু ঘাটতিটুকু রাখে; ফলাফল খালি মানে কোনো ঘাটতি নেই। ([../operations.md](../operations.md)-এ এই trick আছে।)
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`"a","b"`: note চায় `a:1`, magazine-এ `a` নেই (`mag_counts['a']=0 < 1`) → `False`। `"aa","ab"`: `a` লাগে 2, আছে 1 → `False`। `"aa","aab"`: `a` লাগে 2, আছে 2 → কোনো ঘাটতি নেই → `True`। `"","anything"`: note খালি, কোনো চাহিদাই নেই → `True`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n + m)** — `n` = note-এর দৈর্ঘ্য, `m` = magazine-এর দৈর্ঘ্য; দুটো একবার করে গোনা, তারপর note-এর distinct অক্ষরে loop।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(k)** — `k` = distinct অক্ষরের সংখ্যা (lowercase English হলে বড়জোর 26, কার্যত O(1))।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- তুলনাটা উল্টে দেওয়া — note-এর চাহিদা magazine-এর stock-এর সাথে মেলাও, উল্টোটা নয় (magazine-এ extra অক্ষর থাকলেও কোনো সমস্যা নেই)।
- `mag_counts[ch]` missing key-তে crash করবে ভাবা — `Counter` missing key-তে 0 দেয়, তাই নিরাপদ; কিন্তু সাধারণ `dict` হলে `.get(ch, 0)` লাগত।
- magazine-এর প্রতিটা অক্ষরে loop করা — শুধু note-এ থাকা অক্ষরগুলো নিয়েই ভাবলে চলে, magazine-এর extra অক্ষর গুরুত্বহীন।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Valid Anagram (#3)-এর frequency counting, `==`-এর জায়গায় per-character `>=`। [../patterns.md](../patterns.md)-র Pattern 1 আর [../operations.md](../operations.md)-র Counter subtraction অংশ দেখো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Valid Anagram —