Introduction

This is the classic ransom-note problem: can a target string be formed using the characters available in a source string, where each source character can be used at most once. The solution is to compare character frequencies, not to search greedily for each character one by one.

The reason frequency counting works is simple. If the source contains at least as many of every required character as the target, the note can be built. If even one character is short, the answer is false.

Frequency Counting Approach

The direct algorithm is:

1. count how many times each character appears in the magazine
2. scan the target string
3. decrement the corresponding count for each needed character
4. fail if any count would go negative

This runs in linear time with respect to the total input size.

A Runnable Python Example

1def can_build(note, magazine):
2    counts = {}
3
4    for ch in magazine:
5        counts[ch] = counts.get(ch, 0) + 1
6
7    for ch in note:
8        if counts.get(ch, 0) == 0:
9            return False
10        counts[ch] -= 1
11
12    return True
13
14
15print(can_build("help", "hello planet"))
16print(can_build("apple", "pale"))

This works because each magazine character is consumed at most once through the decrement step.

Why Greedy Search Is Worse

A naive approach might search the magazine from scratch for every character in the note. That works functionally, but it is inefficient because it repeats work and tends toward quadratic behavior on long inputs.

Counting frequencies once avoids that repeated scanning.

Fixed Character Sets

If the problem guarantees only lowercase English letters, you can replace the dictionary with an array of length 26:

1def can_build_lowercase(note, magazine):
2    counts = [0] * 26
3
4    for ch in magazine:
5        counts[ord(ch) - ord('a')] += 1
6
7    for ch in note:
8        index = ord(ch) - ord('a')
9        if counts[index] == 0:
10            return False
11        counts[index] -= 1
12
13    return True

This is a little faster and uses fixed space, but only when the character domain is known in advance.

Practical Edge Cases

Decide upfront whether:

• case matters
• spaces matter
• punctuation matters
• Unicode characters are allowed

Those are problem-definition choices, not algorithm changes. The counting approach still works, but the character domain and normalization rules need to match your requirements.

Why Decrementing Is Better Than Comparing Two Full Maps

You could count both strings fully and compare the maps afterward, but decrementing while scanning the target lets you fail early. As soon as one needed character is unavailable, the answer is already false and there is no reason to keep processing the rest of the note.

Time and Space Complexity

With a dictionary-based counter:

• time complexity is O(m + n)
• space complexity is O(k), where k is the number of distinct characters tracked

With a fixed alphabet array, the extra space can be treated as constant.

Common Pitfalls

• Scanning the magazine repeatedly instead of counting once.
• Forgetting that each source character can be used only once.
• Ignoring case sensitivity or punctuation rules in the problem statement.
• Assuming fixed-size arrays work even when the input can contain arbitrary Unicode.
• Removing characters from immutable strings directly and making the solution slower than necessary.

Summary

• The right solution is frequency counting, not repeated searching.
• Count source characters, then consume counts while scanning the target.
• The algorithm runs in linear time.
• Arrays are great for fixed alphabets; dictionaries are safer for general text.
• Define case and punctuation rules clearly before implementing the check.