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.

class Solution:
    def canConstruct(self, 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, that’s ~10^10 character comparisons in the worst case — hopeless. All that scanning just to answer “is there an unused e left?”, which a counter answers in O(1).

Approach 2 — Hash map of counts (Counter)

The insight: 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 26 numbers.

from collections import Counter


class Solution:
    def canConstruct(self, 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

The insight: with a known tiny alphabet you don’t need a hash map at all. Count the magazine into a length-26 array, then spend from it while reading the note; the first letter that would go negative proves failure. One array, no second counter.

class Solution:
    def canConstruct(self, 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, but constant-factor faster and a classic interview refinement worth naming.

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 — and when the alphabet is small and fixed, downgrade the hash map to a flat array indexed by symbol. The same skeleton solves anagram checks, permutation-in-string, and every “do the letters suffice?” variant.