Learning Outcome
After this lesson, you should be able to use a frequency table as an availability inventory and consume characters safely.
Problem Statement
Given ransomNote and magazine, return true if ransomNote can be constructed using each magazine character at most once.
| Input | Output | Why |
|---|---|---|
ransomNote = "aa", magazine = "aab" | true | The magazine has two a characters, enough to build aa. |
Brute Force Approach
For each ransom character, scan the magazine for an unused matching character. This is slow and awkward to track.
Optimized Approach
Count magazine characters once. For each ransom character, decrement its available count and fail immediately if it goes below zero.
Exact Pseudocode
freq = counts of magazine
for ch in ransomNote:
freq[ch] -= 1
if freq[ch] < 0:
return false
return trueReference Code
class Solution:
def canConstruct(self, ransomNote, magazine):
freq = {}
for ch in magazine:
freq[ch] = freq.get(ch, 0) + 1
for ch in ransomNote:
freq[ch] = freq.get(ch, 0) - 1
if freq[ch] < 0:
return False
return TrueSample Dry Run
| Step | State | Result |
|---|---|---|
| Count magazine | a:2, b:1 | Availability ready |
| Need first a | a count becomes 1 | Still possible |
| Need second a | a count becomes 0 | Still possible |
| Finish | No shortage found | return true |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n + m) | Both strings are scanned once. |
| Space | O(1) | For lowercase English letters, the frequency array has fixed size. |
Edge Cases
- An empty ransom note returns true.
- Repeated needed characters require repeated availability.
- Set membership alone is not enough.
Interview Checklist
- Count magazine, not ransomNote, as the available inventory.
- Fail as soon as a count goes below zero.
- Use the right character range for the prompt.
FAQs
Why not use a set?
A set only says whether a character exists, not how many copies are available.
Why decrement while scanning ransomNote?
It simulates consuming each required character once.
What is the core pattern?
Frequency availability counting.