Ransom Note (LeetCode 383)

The problem

You get two strings, ransom and mag. Each letter in the magazine can be used at most once. Return True if you can build ransom from the magazine’s letters, otherwise False.

Input:  ransom = "aa", mag = "aab"
Output: True

Input:  ransom = "aa", mag = "ab"
Output: False

The note needs two as. "aab" has two, but "ab" has only one.

How to think about it

Start with brute force. For each letter of the note, search the magazine for an unused copy and cross it out. Each search is O(m), so that’s O(n·m) for a note of length n and a magazine of length m. Order doesn’t matter at all here, which is a strong hint that you’re doing too much work.

The key insight: only the counts matter. The note is buildable if and only if, for every letter, the note needs no more copies than the magazine has. So count the letters in each string and compare letter by letter. That’s one pass over each string.

Python makes the comparison one expression. Counter subtraction keeps only the positive differences. Counter(ransom) − Counter(mag) is therefore exactly “the letters the magazine is short of”. If that result is empty, nothing is missing and the note can be built. An empty Counter is falsy, so not (…) turns it into True.

Which pattern is this? Hash map frequency counting. The tell is “can A be made from the pieces of B?”, where order is irrelevant.

Approach

1. Count the letters of ransom and of mag.
2. Subtract the magazine counts from the note counts, keeping only letters where the note needs more.
3. If nothing is left, return True; otherwise return False.

Without Counter: fill a 26-slot array from the magazine, then for each note letter subtract one and return False the moment any slot goes negative.

Solution

from collections import Counter

def can_construct(ransom, mag):
    return not (Counter(ransom) - Counter(mag))   # leftover = letters the magazine lacks
# can_construct("aa", "aab") -> True

Dry run

In the first row, a is 2 − 2 = 0 and b is 0 − 1 = −1; both are dropped because they’re not positive, so nothing is short.

Complexity

• Time: O(n + m). One pass to count each string, plus a subtraction over at most 26 distinct letters.
• Space: O(1). With lowercase English letters, each Counter holds at most 26 keys.

Edge cases and pitfalls

• Empty note: always buildable. Counter("") minus anything is empty, so it returns True.
• Extra magazine letters are fine. Negative differences are discarded, which is exactly the behaviour you want.
• Using sets (set(ransom) <= set(mag)) ignores counts and wrongly accepts "aa" from "ab".
• Don’t swap the arguments. Counter(mag) − Counter(ransom) asks the opposite question.
• Early exit: the array version can stop at the first shortage, which matters if the note is huge and fails early.

Related problems

• Valid Anagram (LeetCode 242): the counts must be equal, not just “fit inside”.
• First Unique Character in a String (LeetCode 387): another count-then-scan string problem.
• Minimum Window Substring (LeetCode 76): “does this window contain all the needed letters?”, checked as the window slides.