Ransom Note — The Frequency Availability Hashmap Pattern at FAANG

Problem Statement#

Given two strings ransomNote and magazine, return true if ransomNote can be constructed from the letters of magazine. Each letter of magazine may be used at most once.

Constraints:

• 1 <= ransomNote.length, magazine.length <= 10^5
• Both strings consist of lowercase English letters.

Input:  ransomNote = "aa", magazine = "aab"
Output: true

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

Why This Problem Matters#

LeetCode 383 Ransom Note appears at Amazon, Google, Microsoft, and Meta as a frequency-availability check. The interview signal is whether you treat magazine as a multiset (supply) and ransomNote as a demand, then verify supply covers demand using a HashMap.

The pattern reappears in Find Words That Can Be Formed by Characters, Maximum Number of Balloons, and any inventory-style hashmap interview question. Production analogues include API rate limiters checking remaining quota, warehouse pickers verifying stock, and feature gating checking entitlement counts.

The naive O(n*m) "scan magazine for each note char" answer is the wrong level of FAANG. Hash table FAANG fluency means counting once and consuming once.

The Core Insight#

Build a 26-element supply array from magazine. Then walk ransomNote decrementing supply for each requested character. Return false the moment a counter dips below zero — that proves the magazine cannot cover the note. Return true if the walk completes.

This converts the brute-force quadratic into linear time using O(1) space (26-element array). The same approach scales to Unicode by switching to a dict or Map.

Visual Dry Run#

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

No counter went negative — return true.

Solution (Optimal)#

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        supply = [0] * 26
        for c in magazine:
            supply[ord(c) - 97] += 1
        for c in ransomNote:
            idx = ord(c) - 97
            supply[idx] -= 1
            if supply[idx] < 0:
                return False
        return True

var canConstruct = function(ransomNote, magazine) {
    const supply = new Array(26).fill(0);
    for (const c of magazine) supply[c.charCodeAt(0) - 97]++;
    for (const c of ransomNote) {
        const idx = c.charCodeAt(0) - 97;
        if (--supply[idx] < 0) return false;
    }
    return true;
};

Time: O(n + m) where n and m are string lengths. Space: O(1) for the fixed 26-element supply array.

Common Mistakes#

• Treating magazine as a set, missing repetition counts.
• Iterating ransomNote first to build demand, then comparing — works but is two passes instead of one decrement loop.
• Forgetting to early-return on the first negative counter; you waste cycles walking the rest.
• Using Counter(magazine) - Counter(ransomNote) direction reversed; the correct check is Counter(note) - Counter(mag) should be empty.
• Hardcoding 26 when the follow-up extends to Unicode characters.

Interview Tips#

• Name the pattern: "supply versus demand" or "availability check."
• State O(n + m) time and O(1) space upfront. FAANG graders check this first.
• For Pythonic style, mention not (Counter(ransomNote) - Counter(magazine)) as a one-liner.
• Anticipate the streaming variant: keep persistent supply across many notes.

Follow-up Questions#

• What if characters can be Unicode? (Hint: switch to a HashMap.)
• What if many notes arrive against a single magazine? (Hint: precompute supply, fork per note.)
• What if you must report which letters are missing? (Hint: collect indexes where decrement goes negative.)
• Generalize to Find Words That Can Be Formed by Characters (LC 1160).
• Compare against Valid Anagram. (Hint: anagram is bidirectional, ransom note is one-directional.)

Key Takeaways#

• LeetCode 383 Ransom Note tests the supply-demand hashmap interview pattern.
• The 26-element frequency array gives O(1) space for lowercase ASCII.
• Build supply from magazine, then decrement while walking ransomNote.
• Return false the moment any counter goes negative.
• The same pattern handles inventory, rate limiting, and entitlement checks in production.
• Switch to a HashMap for Unicode support without changing the algorithm.
• One-liner: not (Counter(note) - Counter(mag)) is concise but allocates more memory.