Ransom Note: Check Letter Supply Against Demand With a Counter

Problem

You are given two strings, note and magazine. Return True if note can be written by cutting letters out of magazine, where each letter in magazine can be used at most once, and False otherwise. Order does not matter. This is LeetCode 383, Ransom Note.

Both strings contain lowercase English letters and are up to about 10^5 characters long.

Examples

note = "tea",   magazine = "eatery"   ->  True
note = "tree",  magazine = "rte"      ->  False   (needs two e's, magazine has one)
note = "",      magazine = "abc"      ->  True    (nothing to build)
note = "a",     magazine = ""         ->  False

Approach 1: brute force

For each letter of the note, find and remove a matching letter from a list copy of the magazine.

def can_construct_brute(note, magazine):
    letters = list(magazine)
    for ch in note:
        if ch not in letters:
            return False
        letters.remove(ch)
    return True

Complexity: O(m · n) time, because each in and remove scans the list. O(n) extra space for the copy.

Approach 2: optimal (frequency count)

Key insight: order is irrelevant, so only the number of copies of each letter matters. Build the supply once, then let the note draw it down.

def can_construct(note, magazine):
    if len(note) > len(magazine):
        return False
    supply = [0] * 26
    for ch in magazine:
        supply[ord(ch) - ord("a")] += 1
    for ch in note:
        i = ord(ch) - ord("a")
        supply[i] -= 1
        if supply[i] < 0:
            return False
    return True

With collections.Counter, the comparison is a one-liner. Counter’s <= checks that every count on the left is at most the matching count on the right (available from Python 3.10).

from collections import Counter

def can_construct_counter(note, magazine):
    return Counter(note) <= Counter(magazine)

Why it is correct: the note can be built exactly when, for every letter, the note needs no more copies than the magazine has. The loop checks that inequality letter by letter as it spends counts, and it fails the moment any letter runs out.

Complexity: O(m + n) time, O(1) extra space for the 26 counters (O(k) for an alphabet of size k).

Tests

import random

for f in (can_construct, can_construct_counter, can_construct_brute):
    assert f("tea", "eatery") is True
    assert f("tree", "rte") is False      # not enough copies of one letter
    assert f("", "abc") is True           # empty note
    assert f("a", "") is False            # empty magazine
    assert f("", "") is True
    assert f("aab", "baa") is True        # exact match of counts
    assert f("abc", "ab") is False        # letter missing entirely

random.seed(9)
for _ in range(500):
    note = "".join(random.choice("abc") for _ in range(random.randint(0, 6)))
    mag = "".join(random.choice("abc") for _ in range(random.randint(0, 8)))
    assert can_construct(note, mag) == can_construct_counter(note, mag) == can_construct_brute(note, mag)

Edge cases and pitfalls

• Count the magazine as supply and subtract the note. Doing it the other way round answers a different question.
• Using a set instead of counts ignores multiplicity: "tree" from "rte" would wrongly pass.
• The 26-slot array assumes lowercase letters; anything else needs a dictionary.
• Counter’s rich comparisons need Python 3.10 or later. On older versions, check not (Counter(note) - Counter(magazine)).

Where this shows up in data engineering

This is a supply-versus-demand check: can the stock on hand cover these orders, or does a target table contain at least as many rows per key as the source? In SQL you aggregate both sides by key, join, and look for keys where demand exceeds supply. Reporting the shortfall instead of a single yes or no is usually what a data quality check needs.