Skip to content

004 — Ransom Note

Source

  • Original source: Classic frequency-count exercise
  • Platform: LeetCode — https://leetcode.com/problems/ransom-note/
  • Topic: hash map / frequency count
  • Difficulty: Easy
  • Pattern: frequency counting
  • Basic idea inherited from: Valid Anagram — তবে "সমান" নয়, "cover করতে পারে কি না" (count coverage)

1. Problem in simple words

দুটো string দেওয়া আছে — ransomNote আর magazine। তুমি magazine-এর অক্ষর কেটে কেটে ransomNote বানাতে চাও। শর্ত: magazine-এর প্রতিটা অক্ষর একবারই ব্যবহার করা যাবে। বলো — ransomNote-টা কি বানানো সম্ভব?

ransomNote = "aa", magazine = "aab"  →  True   (দুটো 'a' আছে, লাগবে দুটো)
ransomNote = "aa", magazine = "ab"   →  False  (একটাই 'a', কিন্তু লাগে দুটো)

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-এ এটাও 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-এর জন্য একদম স্বাভাবিক কাজ।

6. Real-life analogy

ভাবো তুমি রান্না করতে বসেছ আর recipe-তে লাগবে 2টা ডিম, 1 কাপ চিনি। তুমি ফ্রিজ আর প্যান্ট্রির stock গোনো, তারপর প্রতিটা উপকরণে দেখো "যথেষ্ট আছে তো?" একটাও কম পড়লে recipe হবে না। Recipe = ransomNote, প্যান্ট্রি = magazine, গোনা-তালিকা = Counter।

7. Visual explanation

ransomNote = "aa", magazine = "aab"। দুই দিকে count বানাই, তারপর চাহিদা মেলাই:

note  count = {a:2}
mag   count = {a:2, b:1}

চাহিদা 'a': দরকার 2, stock 2  →  2 >= 2  ঠিক আছে
আর কোনো চাহিদা নেই            →  return True

আর কম পড়লে:

note "aa" = {a:2},  mag "ab" = {a:1, b:1}
চাহিদা 'a': দরকার 2, stock 1  →  1 < 2  →  return False

8. Example input and output

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   (কিছুই লাগে না)

9. Brute force thinking

প্রথম সরল চিন্তা: note-এর প্রতিটা অক্ষর magazine-এর একটা list-এ খুঁজে বের করে মুছে দাও (যাতে দুবার ব্যবহার না হয়); কখনো না পেলে অসম্ভব।

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)। প্রশ্নটা "ঠিক একই অক্ষর কি" থেকে সরে গিয়ে "যথেষ্ট অক্ষর কি আছে" হয়ে যায় — একই গোনা, শুধু তুলনাটা এক-দিকের।

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।

15. Python solution

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-এ এই trick আছে।)

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

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 অক্ষর গুরুত্বহীন।

21. Which basic problem this inherits from

ভিত্তি: Valid Anagram (#3)-এর frequency counting, ==-এর জায়গায় per-character >=। ../patterns.md-র Pattern 1 আর ../operations.md-র Counter subtraction অংশ দেখো।

22. Similar harder problems

23. Pattern learned

Frequency counting (coverage): চাহিদা বনাম stock — per-character magazine >= note মেলাও; "X দিয়ে কি Y বানানো যায়" প্রশ্নের মূল চাল।

24. Final summary

ভবিষ্যতের আমাকে: "X দিয়ে কি Y বানানো যায় / যথেষ্ট আছে কি" শুনলেই Counter আর per-character >=। Anagram-এর সমতা একটু আলগা করে দাও coverage-এ — সেটাই Ransom Note, আর সেটাই পরে sliding-window count-matching-এর বীজ।

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