Ransom Note

Problem

You’re given two strings, ransomNote and magazine. Determine whether you can assemble the ransom note by cutting letters out of the magazine: every character of ransomNote must be matched to a distinct character of magazine (each magazine letter can be used at most once). Return True if it’s possible, False otherwise.

In other words: for every letter, does the magazine contain at least as many copies as the note needs?

Examples

• Input: ransomNote = "a", magazine = "b" → Output: False The magazine has no a at all.
• Input: ransomNote = "aa", magazine = "ab" → Output: False The note needs two as but the magazine supplies only one.
• Input: ransomNote = "aab", magazine = "baa" → Output: True The magazine has two as and one b — exactly enough.

Constraints

• 1 <= len(ransomNote), len(magazine) <= 10^5
• Both strings consist of lowercase English letters only

Expected: O(m + n) time. The 26-letter alphabet is a strong hint about the counting structure.

Think about it first

TL;DR

Count letters of both strings and compare per letter — O(m + n) time, O(1) space (26-letter alphabet).

Approach 1 — Brute force: cross letters off a copy

Simulate the cutting literally: for each character of the note, search the magazine for an unused copy and cross it off.

def canConstruct(ransomNote: str, magazine: str) -> bool:
    pool = list(magazine)
    for ch in ransomNote:
        if ch in pool:
            pool.remove(ch)
        else:
            return False
    return True

Complexity: O(n · m) time (each in / remove scans the pool), O(m) space.

With both strings up to 10^5, this is up to ~10^10 comparisons in the worst case. Each scan only answers whether an unused copy of a letter remains, which a count lookup answers in O(1).

Approach 2 — Hash map of counts (Counter)

Order is irrelevant: the note is buildable iff, letter by letter, the magazine’s supply covers the note’s demand. Count both sides once, then compare.

from collections import Counter


def canConstruct(ransomNote: str, magazine: str) -> bool:
    need = Counter(ransomNote)
    have = Counter(magazine)
    return all(have[ch] >= cnt for ch, cnt in need.items())

Equivalently, not (need - have) — Counter subtraction keeps only positive deficits.

Walkthrough on ransomNote = "aab", magazine = "baa":

1. need = {a: 2, b: 1}, have = {b: 1, a: 2}.
2. Check a: have 2 ≥ need 2 — ok.
3. Check b: have 1 ≥ need 1 — ok.
4. All letters covered → True. Matches the expected output.

On "aa" vs "ab": need = {a: 2}, have = {a: 1, b: 1}; check a: 1 ≥ 2 fails → False.

Complexity: O(m + n) time; O(1) space — at most 26 keys per counter.

Approach 3 — Fixed 26-slot array, single decrement pass

With a fixed, small alphabet, a hash map is unnecessary. Count the magazine into a length-26 array, then subtract from it while reading the note; the first letter that goes negative proves failure. This uses one array and no second counter.

def canConstruct(ransomNote: str, magazine: str) -> bool:
    counts = [0] * 26
    base = ord("a")
    for ch in magazine:
        counts[ord(ch) - base] += 1
    for ch in ransomNote:
        i = ord(ch) - base
        counts[i] -= 1
        if counts[i] < 0:
            return False
    return True

Walkthrough on "aab" vs "baa": after counting the magazine, slot a = 2, slot b = 1. Spending the note: a → a becomes 1; a → a becomes 0; b → b becomes 0. Nothing went negative → True.

Complexity: O(m + n) time, O(1) space (exactly 26 integers). Same asymptotics as the Counter, with a smaller constant factor.

Common pitfalls

• Comparing sets of letters instead of counts — "aa" vs "ab" shares the letter set {a} on the demand side but fails on multiplicity.
• Decrement-pass order matters: count the magazine first and spend with the note. Doing it backwards flips the inequality and accepts wrong answers.
• The tempting one-liner all(ch in magazine for ch in ransomNote) ignores multiplicity entirely — and hides an O(n·m) scan besides.
• Early-exit idea worth keeping: if len(ransomNote) > len(magazine), the answer is False before any counting.

Pattern takeaway

“Can A be assembled from the letters of B?” is a multiset containment question: order never matters, only per-symbol counts. Hash-count both sides and compare; when the alphabet is small and fixed, replace the hash map with a flat array indexed by symbol. The same skeleton solves anagram checks, permutation-in-string, and other “do the letters suffice?” variants.