Ransom Note: A Counting Problem in Five Lines

The problem

Given ransomNote and magazine, return true if the note can be built using letters from the magazine, each magazine letter used at most once.

Count the supply, spend the demand

from collections import Counter

def can_construct(note, magazine):
    supply = Counter(magazine)
    for ch in note:
        if supply[ch] == 0:
            return False
        supply[ch] -= 1
    return True

O(m + n) time and O(1) space for a fixed alphabet. Returning as soon as a letter runs out keeps the common failing case fast.

The one-liner

not (Counter(note) - Counter(magazine)) works because Counter subtraction drops non-positive counts. It is neat, but explain it: interviewers want to know you know why it works.

Edge cases

Follow-up: a huge magazine

If the magazine is a stream too big to store, count the note instead and decrement as magazine letters arrive, stopping once every count reaches zero. That flips which side you store and is the answer to "what if memory is tight".


Disclosure: I work on Linkjob AI. If you want structured practice for interviews like this, https://www.linkjob.ai/ can help you rehearse and get real-time hints.