Ransom Note

You want to write the message ransomNote by cutting individual letters out of the text magazine and gluing them together.

Each letter cut from the magazine can be used only once, but the letters may be taken from anywhere and in any order. Return true if the magazine contains enough copies of every letter to spell the note, and false otherwise.

Both strings consist only of lowercase English letters.

Example 1

Example 2

Example 3

Constraints

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote and magazine consist of lowercase English letters.

Pattern Path · Hashing & Counting · problem 3 of 169

Start simple

For each letter of the note, search the magazine for an unused copy and mark it as used: O(n·m) time.

The key idea

Since letters can be taken from anywhere, the magazine is really just a bag of letters: all that matters is how many of each it holds. The note can be built exactly when, for every letter, the note needs no more copies than the magazine has.

Count the magazine's letters in a table (a hash map, or an array of 26 counters). Then go through the note one letter at a time and use one copy: if the count for that letter is already zero, there is no copy left, so return false; otherwise decrement it. If every letter of the note is covered, return true.

This reads each string once, so it takes linear time. The table has at most 26 entries, so the extra space is constant. A quick early exit is possible too: a note longer than the magazine can never be built.

Complexity

• Time: O(n + m)
• Space: O(1)

Python

from collections import Counter


class Solution:
    def canConstruct(self, ransomNote, magazine):
        available = Counter(magazine)
        for ch in ransomNote:
            if available[ch] == 0:  # no unused copy of this letter is left
                return False
            available[ch] -= 1
        return True

JavaScript

var canConstruct = function(ransomNote, magazine) {
  const available = new Array(26).fill(0);
  const A = 'a'.charCodeAt(0);
  for (let i = 0; i < magazine.length; i++) available[magazine.charCodeAt(i) - A]++;
  for (let i = 0; i < ransomNote.length; i++) {
    const k = ransomNote.charCodeAt(i) - A;
    if (available[k] === 0) return false; // no unused copy of this letter is left
    available[k]--;
  }
  return true;
};

What the interviewer is checking

The interviewer wants you to reduce the problem to comparing letter counts and implement it cleanly with a counter, ideally noting that the alphabet size bounds the memory.

Mistakes to avoid

• Checking only that each note letter appears somewhere in the magazine, ignoring how many times it is needed.
• Counting the note and the magazine but comparing in the wrong direction (the magazine may have extra letters).
• Using string search and removal (e.g. replacing characters in a string) inside a loop, which turns the solution quadratic.

Follow-ups to expect

• What if words, not letters, are cut out? (Count whole words instead.)
• What if the magazine is a huge stream? (Count note needs, decrement while streaming.)
• What if uppercase and symbols are allowed? (Use a hash map instead of 26 slots.)

In real software

Checking whether available stock covers an order, or whether a set of resources satisfies a request, is the same counts-cover-needs check used in inventory and scheduling systems.

Practice next