Ransom Note LeetCode 383 Deep Dive

LeetCode 383 — Ransom Note — gives you two strings: ransomNote and magazine. Your task is to return true if ransomNote can be constructed by using the letters from magazine, where each character in magazine may be used at most once. If the magazine does not supply enough of any character needed by the ransom note, return false.

The problem models a classic supply-and-demand scenario: the magazine is your supply of characters, and the ransom note expresses the demand. You need to verify that supply meets or exceeds demand for every distinct character. A single missing character is enough to make the note impossible to construct.

The problem is rated Easy and appears frequently in coding interviews as an entry-level frequency-counting question. It tests whether you recognize the supply-and-demand character counting pattern and choose an efficient data structure — a hash map or a fixed-size integer array — over a naive nested-loop approach.

The core algorithm has two phases. First, count every character in the magazine to build a frequency map representing available supply. Then iterate through each character of the ransom note: decrement its count in the frequency map. If any decrement causes the count to drop below zero, supply is exhausted for that character and you return false immediately. If all characters are accounted for, return true.

This single-pass-per-string approach runs in O(n+m) time where n is the length of ransomNote and m is the length of magazine. The frequency map holds at most 26 entries for lowercase letters, giving O(1) space. No sorting, no nested loops, and no revisiting characters — each character is processed exactly once in each string.

The early-exit optimization is meaningful for large inputs: if the ransom note needs a character that appears nowhere in the magazine, you detect it on the very first encounter and return false without scanning the rest of the note. In practice this makes the approach feel near-instant for inputs where the note is clearly impossible.

Python's collections.Counter provides an elegant one-liner: Counter(ransomNote) - Counter(magazine). Counter subtraction discards zero and negative counts, so if Counter(ransomNote) - Counter(magazine) is empty (evaluates to an empty Counter, which is falsy), every character needed by the note was sufficiently supplied by the magazine and you can return true.

If the subtraction result is non-empty, it contains the characters still needed after exhausting the magazine — meaning the note cannot be formed. This approach is extremely readable and idiomatic Python, and it is correct because Counter subtraction never produces negative values; a character with zero remaining supply in the magazine simply saturates at zero rather than going negative.

Under the hood, Counter subtraction does exactly the same work as the explicit loop approach: it iterates through the note's character counts and subtracts magazine counts, keeping only positive remainders. The time and space complexity are identical — O(n+m) time, O(1) space for lowercase letters. Choose between them based on whether you prefer terseness or explicitness.

For lowercase English letters only, an int[26] array indexed by character (c - 'a') is faster than a HashMap in practice. Array access is direct memory addressing with no hashing overhead, no collision resolution, and guaranteed O(1) per operation with tiny constants. The array is always exactly 26 integers — about 104 bytes — making it cache-friendly and allocation-free compared to a HashMap with its buckets and load factor management.

For Unicode inputs or when the character set is unknown, a HashMap is the flexible choice. It handles any character range without pre-sizing assumptions and scales naturally to thousands of distinct characters. The trade-off is slightly higher constant factors and heap allocation. If the problem explicitly states lowercase English letters, prefer the array; otherwise, default to HashMap for correctness across all inputs.

Both data structures give O(n+m) time complexity where n is the note length and m is the magazine length, and both use O(1) space for fixed alphabets or O(k) space for k distinct characters. The choice between them is a constant-factor performance decision, not an asymptotic one. In interviews, stating both options and explaining the trade-off demonstrates deeper understanding than just picking one.

Example 1: ransomNote="aa", magazine="aab". Build magazine frequency: {a:2, b:1}. Now iterate the note: first 'a' decrements a to 1; second 'a' decrements a to 0. No count went negative. Return true — the magazine supplies two a's and the note only needs two.

Example 2: ransomNote="aa", magazine="ab". Build magazine frequency: {a:1, b:1}. Iterate the note: first 'a' decrements a to 0; second 'a' tries to decrement a from 0 to -1 — negative count detected. Return false immediately. The magazine has only one 'a' but the note demands two.

The two examples illustrate the boundary: the magazine must supply at least as many of each character as the note demands. Extra magazine characters (like the 'b' in both examples) are irrelevant — they simply go unused. The algorithm never checks whether magazine characters are used; it only checks whether note demand is satisfied.

Python Counter one-liner: from collections import Counter; def canConstruct(ransomNote, magazine): return not (Counter(ransomNote) - Counter(magazine)). The subtraction drops zero/negative counts; if the result is empty, all demands were met. Alternatively, the explicit loop: count = Counter(magazine); for c in ransomNote: count[c] -= 1; if count[c] < 0: return False; return True.

Python array version for constant-factor optimization: freq = [0] * 26; for c in magazine: freq[ord(c) - ord('a')] += 1; for c in ransomNote: freq[ord(c) - ord('a')] -= 1; if freq[ord(c) - ord('a')] < 0: return False; return True. The int[26] version avoids dict overhead and is faster on large inputs even though the asymptotic complexity is the same.

Java array version: public boolean canConstruct(String ransomNote, String magazine) { int[] freq = new int[26]; for (char c : magazine.toCharArray()) freq[c - 'a']++; for (char c : ransomNote.toCharArray()) { if (--freq[c - 'a'] < 0) return false; } return true; }. The pre-decrement in the condition check is idiomatic Java: decrement then immediately check, returning false as soon as any count goes negative. Time O(n+m), space O(1).

Valid Anagram (LeetCode 242) is the closest relative: same int[26] or Counter approach, but requires exact frequency equality rather than a subset check. Group Anagrams (LeetCode 49) extends Valid Anagram by grouping all anagrams together using a frequency tuple as a hash key — the same counting idea applied at scale across a list of strings.

Maximum Number of Balloons (LeetCode 1426) uses the supply-and-demand pattern directly: count characters in the input text, then determine how many times the word "balloon" can be formed given the available frequencies, accounting for repeated letters ('l' and 'o' each appear twice). Find All Anagrams in a String (LeetCode 438) applies a sliding window over a frequency array to find all starting positions where a window matches the target character counts.

The frequency counting family — Ransom Note (383), Valid Anagram (242), Group Anagrams (49), Max Balloons (1426), Find Anagrams (438), and Minimum Window Substring (76) — forms a progression from simple supply checks to sliding window frequency maintenance. Mastering the int[26] array and Counter subtraction patterns at the Ransom Note level unlocks the intuition for all the harder variants.