File: ransom-note/solution.py

Date: 2026-06-06

Time: 18:38

ransom-note/solution.py

Purpose

This file implements the solution to LeetCode 383 — Ransom Note. It determines whether a ransom note string can be constructed by using each letter from a magazine string at most once. It owns exactly one responsibility: the can_construct function.

Key Components

canconstruct(ransomnote: str, magazine: str) -> bool

The sole public function. It returns True if every character in ransom_note appears in magazine with at least the required frequency.

The implementation is a single expression:

return not (Counter(ransom_note) - Counter(magazine))

Patterns

Counter subtraction idiom. Counter subtraction drops zero and negative counts, keeping only characters where ransomnote has a surplus over magazine. If the resulting Counter is empty (falsy), every character was available — so not emptycounter evaluates to True.

This is a common Python idiom for "multiset subset" checks: A is a sub-multiset of B iff A - B is empty.

Dependencies

Imports: collections.Counter — the only dependency. No custom modules.

Imported by: The ransom-note/testsolution.py file imports this function directly. The large "imported by" list in the context is an artifact of the repo's test infrastructure — those test files don't import canconstruct; they share a common test runner pattern that indexes all solution modules.

Flow

1. Build a Counter (character frequency map) for ransom_note.

2. Build a Counter for magazine.

3. Subtract: for each character, compute countinnote - countinmagazine. Counter._sub_ discards keys where the result is zero or negative.

4. If any key survives (positive count), the note needs more of that character than the magazine provides → the Counter is truthy → not truthy → return False.

5. If empty → not {} → return True.

Time complexity: O(n + m) where n = len(ransom_note), m = len(magazine).

Space complexity: O(1) — bounded by alphabet size (at most 26 lowercase English letters per the problem constraints).

Invariants

• Each magazine letter is consumed at most once (enforced by the subtraction semantics of Counter).
• The function is pure — no mutation of inputs, no side effects.
• Both arguments are expected to be strings. No explicit validation; the function relies on Counter accepting any iterable.

Error Handling

None. The function delegates entirely to Counter, which will raise TypeError if given a non-iterable. Empty strings are handled correctly: Counter("") - Counter(anything) produces an empty Counter, returning True (an empty note can always be constructed).