Ransom Note: Frequency Counting with Available Supply

LeetCode 383, Ransom Note, asks whether you can construct a ransom note string using only the characters available in a magazine string. Each magazine character can only be used once. If you have already solved Valid Anagram, this problem will feel very familiar, but with a twist: instead of checking if two strings have identical character frequencies, you are checking if one string's frequencies are a subset of the other's.

This is one of the cleanest frequency counter problems on LeetCode. Let's walk through it.

The problem

Given two strings ransomNote and magazine, return True if ransomNote can be constructed by using the letters from magazine, and False otherwise. Each letter in magazine can only be used once in ransomNote.

Example: ransomNote = "aab", magazine = "aabbc". The answer is True because the magazine contains at least two 'a's and one 'b', which is everything the ransom note needs.

The question boils down to: does the magazine have enough of every character that the ransom note requires?

The key insight: supply vs demand

Think of the magazine as a supply of characters. The ransom note is a demand. For each character in the ransom note, you need the magazine to have at least that many copies available. If the magazine runs short on any single character, the answer is False.

This is a direct application of the frequency counter pattern. Count the supply (magazine), then walk through the demand (ransom note) and decrement. If any count drops below zero, the supply was not enough.

The solution

def can_construct(ransom_note: str, magazine: str) -> bool:
    freq = {}
    for ch in magazine:
        freq[ch] = freq.get(ch, 0) + 1

    for ch in ransom_note:
        freq[ch] = freq.get(ch, 0) - 1
        if freq[ch] < 0:
            return False

    return True

Let's break each piece down:

• Count the magazine. Walk through every character in magazine and record its frequency. This builds your supply map.
• Consume for the ransom note. Walk through every character in ransomNote and decrement its count in the frequency map. If you have never seen that character, freq.get(ch, 0) handles it by starting from 0 before subtracting.
• Check for shortage. After each decrement, if the count drops below zero, that means the ransom note needs more of that character than the magazine provides. Return False immediately.
• All clear. If you make it through the entire ransom note without running short, return True.

One pass through the magazine, one pass through the ransom note. Each dictionary operation is O(1).

Time: O(m + n) where m is the length of the magazine and n is the length of the ransom note.

Space: O(1) since the character set is bounded at 26 lowercase English letters. The frequency map never grows beyond 26 entries.

Step-by-step walkthrough

Let's trace through ransomNote = "aab", magazine = "aabbc" to see the supply-and-consume approach in action.

Notice how the algorithm short-circuits. The moment any character drops below zero, we stop immediately. There is no need to process the rest of the ransom note. In the best case, this early exit saves significant work.

What about a failing case?

Consider ransomNote = "aa", magazine = "ab". The magazine has only one 'a'. When we process the second 'a' from the ransom note, the count drops to -1. We return False right away.

# magazine freq: {'a': 1, 'b': 1}
# process first 'a': freq['a'] = 0   (OK)
# process second 'a': freq['a'] = -1  (shortage! return False)

Alternative: Counter subtraction

Python's Counter gives you a one-liner approach:

from collections import Counter

def can_construct(ransom_note: str, magazine: str) -> bool:
    return not (Counter(ransom_note) - Counter(magazine))

When you subtract two Counters, the result only keeps entries with positive counts (characters where the ransom note needs more than the magazine provides). If the result is empty, the magazine covers everything.

This is clean but less transparent. The explicit version is better for interviews because it shows you understand the mechanics of frequency counting and early termination.

Alternative: fixed-size array

Since the problem constrains input to lowercase English letters, you can use a fixed-size array of 26 integers:

def can_construct(ransom_note: str, magazine: str) -> bool:
    count = [0] * 26
    for ch in magazine:
        count[ord(ch) - ord('a')] += 1
    for ch in ransom_note:
        count[ord(ch) - ord('a')] -= 1
        if count[ord(ch) - ord('a')] < 0:
            return False
    return True

Same logic, but avoids hash overhead entirely. The tradeoff is readability and flexibility. For Unicode or mixed-case input, the dictionary version is more adaptable.

Complexity comparison

*O(1) because the character set is bounded at 26 lowercase letters.

All three approaches have the same asymptotic complexity. The dictionary approach is the most readable and the one interviewers expect. The array approach is marginally faster in practice. The Counter one-liner is great for quick scripts but hides the mechanics.

Edge cases to watch for

• Empty ransom note. An empty string can always be constructed. Return True immediately.
• Empty magazine. If the ransom note is non-empty but the magazine is empty, you cannot construct anything. The first character check will fail.
• Ransom note longer than magazine. If len(ransomNote) is greater than len(magazine), you can add an early exit before counting. Not strictly necessary since the frequency check handles it, but it is a free O(1) optimization.
• Identical strings. If ransomNote == magazine, every count ends at exactly zero. Return True.

The building blocks

This problem is built from one core building block:

Frequency counter

The act of counting how many times each element appears in a collection and then using those counts for comparison. The template:

freq = {}
for item in collection:
    freq[item] = freq.get(item, 0) + 1

In the ransom note problem, you count the magazine (supply), then walk the ransom note (demand) and decrement. If any count goes negative, the supply is insufficient.

This same building block powers:

• Valid Anagram: count both strings, check if all counts are equal
• Longest Palindrome: count characters, sum up pairs
• Top K Frequent Elements: count frequencies, extract the k largest
• Sliding window problems: maintain a frequency map that updates as the window moves

The difference between ransom note and valid anagram is subtle but important. Valid anagram checks for exact equality of frequencies (are these two bags identical?). Ransom note checks for a subset relationship (is one bag contained within the other?). In code, the difference is just one comparison: != 0 vs < 0.

Ransom Note vs Valid Anagram

Since these two problems are so closely related, here is a quick comparison:

If you can solve one, you can solve the other with a one-line change. That is the power of recognizing shared building blocks across problems.

Problems that use the same bricks

Once you have frequency counting down, try these:

• Valid Anagram: the sibling problem, checking for exact frequency match instead of a subset
• Longest Palindrome: count character frequencies, then greedily pair them to build the longest palindrome
• Group Anagrams: use frequency counting to generate hash map keys for grouping strings
• First Unique Character in a String: count frequencies, scan for the first with count 1
• Minimum Window Substring: frequency counting inside a sliding window, one of the hardest applications of this pattern

Why this matters beyond the interview

Ransom note is easy. It is rated Easy on LeetCode, and for good reason. But the underlying pattern is not easy. Frequency counting is a fundamental technique that appears in problems across every difficulty level. The ransom note version is the simplest possible "supply vs demand" check, but the same logic extends to:

• Checking if a window contains all required characters (minimum window substring)
• Verifying that a permutation exists within a larger string
• Validating resource constraints in scheduling problems

Drilling the simple version until it is automatic means you do not waste mental energy on the counting mechanics when harder problems layer additional complexity on top.

Related posts

• Valid Anagram - The sibling problem: exact frequency match instead of a supply-vs-demand subset check
• Longest Palindrome - Another frequency counting problem that builds on the same pattern, using character pairs to construct palindromes