Faangprep Logo
Log inStart free
Browse curriculum

Ransom Note

Decide whether a ransom note can be built from a magazine's letters by counting the magazine in a hash map and spending one count per note letter.

EasySolve on LeetCode

Problem Understanding

Ransom Note: given strings ransomNote and magazine, return true if the note can be built from the magazine's letters. Each magazine letter can be used only once.

Example: ransomNote = "aa", magazine = "aab" returns true; with magazine = "ab" it returns false, because there is only one a.

The Intuition: A Budget of Letters

Order does not matter, only how many of each letter you have. So treat the magazine as a budget kept in a hash map:

  1. Count every letter the magazine offers.
  2. For each letter the note needs, spend one. If its count is already 0, the budget is exhausted: return false.
  3. If the note is finished, return true.

It is the same counting idea as Valid Anagram, except that leftover letters are allowed here.

Interactive Walkthrough

The magazine is counted first, then the note spends its letters; the counts still available are beside the figure. Try Example 2 to see the note run out of a.

Dry Run Table

Input: ransomNote = "aa", magazine = "ab"

Phase Letter Counts after
count a a:1
count b a:1, b:1
spend a a:0, b:1
spend a a is 0: fail

Answer: false.

The Solution Template

A 26-slot count array (Python uses Counter): count the magazine, spend on the note.

Ransom Note Code
1var canConstruct = function(ransomNote, magazine) {
2    const counts = new Array(26).fill(0);
3    for (const c of magazine) counts[c.charCodeAt(0) - 97]++;
4    for (const c of ransomNote) {
5        const k = c.charCodeAt(0) - 97;
6        if (counts[k] === 0) return false;
7        counts[k]--;
8    }
9    return true;
10};

Edge Cases & Common Mistakes

  • Note longer than magazine: it can never be built; you can return false immediately as a shortcut.
  • Reusing a letter: each magazine letter counts once; decrement after every use.
  • Extra magazine letters: fine, unlike Valid Anagram.
  • Sorting both strings: works but costs O(n log n); counting is linear.
  • Checking count < 0 after decrementing: also correct, as long as you check before moving on.

Summary

Count the magazine's letters, then spend one for each letter of the note, failing as soon as a needed letter has a count of 0. O(m + n) time and O(1) space with a 26-slot array.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Word Pattern

Next

First Unique Character in a String

The approach, step by step

  1. Count the magazine

    Increment a count for every letter of the magazine.

  2. Spend for the note

    For every letter of the note, if its count is 0 return false; otherwise decrement it.

  3. Return true

    If every note letter was found, the note can be built.

Frequently asked questions

How do you solve Ransom Note efficiently?

Count how many of each letter the magazine has, using a hash map or a 26-slot array. Then walk the note and decrement the count of each letter it needs. If a count is already 0 when the note needs that letter, return false; if the note finishes, return true.

Why not search the magazine for each letter?

Searching and removing letters from the magazine is O(m · n). A count array answers each lookup in O(1), so the whole check is linear.

How is Ransom Note different from Valid Anagram?

Valid Anagram needs the two strings to have exactly the same counts. Ransom Note only needs the magazine to have at least as many of each letter as the note, so leftover magazine letters are fine.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description