C++ 0383.cpp
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
vector<int> letters(256, 0);
for (auto c : magazine)
letters[c]++;
for (auto c : ransomNote)
{
if (letters[c] == 0)
return false;
letters[c]--;
}
return true;
}
};
Difficulty
and has an acceptance rate of about 66% (3+ million submissions).
Typical patterns to solve this problem:
- Counting
- Hash Table
- String
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The presented implementation determines whether a ransom note can be assembled from the letters available in a magazine. It does so by counting the frequency of each character in the magazine and then decrementing those counts while scanning the ransom note. If any required character is missing, the function returns false; otherwise it returns true after all characters have been satisfied.
Key Steps
Counting Characters
The first phase creates a fixed-size frequency table for all possible byte values (0-255). Each character from the magazine string increments the corresponding entry.
vector<int> letters(256, 0);
for (auto c : magazine)
letters[c]++;
The use of a vector<int> sized to 256 ensures constant-time access for any character and eliminates the need for dynamic resizing or hash-based structures.
Validating the Ransom Note
The second phase iterates over the ransomNote. For each character it checks the pre-computed count. If the count is zero, the required letter is unavailable and the function returns false immediately. Otherwise the count is decremented, reflecting the consumption of that letter.
for (auto c : ransomNote)
{
if (letters[c] == 0)
return false;
letters[c]--;
}
If the loop completes without triggering the early return, every character in the note has been matched, and the function returns true.
Edge Cases Handled
The algorithm gracefully handles an empty ransomNote. Since the validation loop never executes, the function reaches the final return true;, correctly indicating that an empty note can always be constructed.
When the magazine is empty but the ransomNote contains characters, the frequency table remains all zeros. The first character examined from the note triggers the letters[c] == 0 condition, causing an immediate false result. This covers the scenario where no source material is available.
Both input strings may contain any ASCII character, including null bytes, punctuation, or whitespace. Because the frequency table indexes directly by the unsigned character value, all possible byte values are accounted for without special casing.
Performance Optimizations
The solution employs a fixed-size array (vector<int> of length 256) to achieve O(1) lookup and update for each character. This eliminates overhead associated with associative containers such as unordered_map. The choice of a plain integer counter avoids the need for additional indirection.
The early-exit condition inside the note-validation loop provides a short-circuit path: as soon as a missing character is detected, the function stops processing further characters. This can dramatically reduce work when the note contains a character not present in the magazine, especially for long inputs.
By iterating over each string exactly once, the implementation minimizes the number of passes over the data, keeping the overall work proportional to the combined length of the two strings. The use of range-based for loops yields concise code while allowing the compiler to generate efficient iterator code.
ELI5 - Simplified Explanation
Imagine having a big pile of magnetic alphabet letters that came from a magazine. You want to see if you can build a secret ransom note using only those specific letters.
Inside the computer, there is a giant tray with two hundred and fifty-six little slots, one for every possible letter. First, the code picks up every single letter from the magazine and puts it into its matching slot in the tray. This way, it keeps a perfect count of exactly how many of each letter are available to use.
Next, the code looks at every letter needed for the secret note one by one. For each letter, it checks the tray to see if there is at least one left. If a slot is empty, that means the note cannot be built because a piece is missing. If there is a letter waiting in the slot, the code takes it out and moves to the next part of the note. After checking every letter needed for the note, if everything was found, the job is finished.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||||
| www | AlgoMonster | C++ | Java | Python | TS | ||||||||
| WalkCCC | C++ | Java | Python | ||||||||||
| leetcode.ca | C++ | Java | Python | Go | C# | PHP | TS | ||||||
| LeetcodeHelp | C++ | Java | Python | ||||||||||
| Progiez | C++ | Java | Python | ||||||||||
| github | AdelDaniel | Dart | |||||||||||
| BigEggStudy | C# | ||||||||||||
| black-shadows | C++ | ||||||||||||
| chandansgowda | Python | ||||||||||||
| charles-wangkai | Java | ||||||||||||
| DimitrisJim | C | ||||||||||||
| everthis | JS | ||||||||||||
| fartem | Ruby | ||||||||||||
| fpdjsns | C++ | ||||||||||||
| halfrost | Go | ||||||||||||
| haoel | C++ | ||||||||||||
| JoshCrozier | JS | ||||||||||||
| keineahnung2345 | C++ | ||||||||||||
| Krazune | C++ | ||||||||||||
| linouk23 | C++ | ||||||||||||
| lkwq007 | Python | ||||||||||||
| lzl124631x | C++ | ||||||||||||
| muhammadfarhankt | Go | ||||||||||||
| qiyuangong | Java | ||||||||||||
| ruoru | Rust | ||||||||||||
| sonugiri1043 | C++ | ||||||||||||
| suxrobGM | C# | ||||||||||||
| varunu28 | Java | ||||||||||||
| vli02 | C | ||||||||||||
| vthwang | Java | ||||||||||||
| XiaotaoGuo | C++ | ||||||||||||
| zfang399 | C++ | ||||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||||
| WalkCCC | C++, Python, Java | ||||||||||||
| leetcode.ca | C++, C#, Go, Java, PHP, Python, TypeScript | ||||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||||
| Progiez | C++, Java, Python | ||||||||||||
| AdelDaniel | Dart | ||||||||||||
| BigEggStudy | C# | ||||||||||||
| black-shadows | C++, C++ | ||||||||||||
| chandansgowda | Python | ||||||||||||
| charles-wangkai | Java | ||||||||||||
| DimitrisJim | C | ||||||||||||
| everthis | JavaScript | ||||||||||||
| fartem | Ruby | ||||||||||||
| fpdjsns | C++ | ||||||||||||
| halfrost | Go | ||||||||||||
| haoel | C++ | ||||||||||||
| JoshCrozier | JavaScript | ||||||||||||
| keineahnung2345 | C++ | ||||||||||||
| Krazune | C++ | ||||||||||||
| linouk23 | C++ | ||||||||||||
| lkwq007 | Python | ||||||||||||
| lzl124631x | C++ | ||||||||||||
| muhammadfarhankt | Go | ||||||||||||
| qiyuangong | Java | ||||||||||||
| ruoru | Rust | ||||||||||||
| sonugiri1043 | C++ | ||||||||||||
| suxrobGM | C# | ||||||||||||
| varunu28 | Java | ||||||||||||
| vli02 | C | ||||||||||||
| vthwang | Java | ||||||||||||
| XiaotaoGuo | C++ | ||||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 691: Stickers to Spell Word
- problem 1160: Find Words That Can Be Formed by Characters
Solved On The Same Day
- problem 125: Valid Palindrome
- problem 191: Number of 1 Bits
- problem 202: Happy Number
- problem 217: Contains Duplicate
- problem 219: Contains Duplicate II
- problem 290: Word Pattern
- problem 392: Is Subsequence
- problem 1047: Remove All Adjacent Duplicates In String
- problem 1089: Duplicate Zeros
- problem 151: Reverse Words in a String
- problem 187: Repeated DNA Sequences
- problem 51: N-Queens
- problem 52: N-Queens II
- problem 60: Permutation Sequence
- problem 68: Text Justification
- problem 76: Minimum Window Substring
- problem 135: Candy
- problem 140: Word Break II
- problem 220: Contains Duplicate III
- problem 239: Sliding Window Maximum
- problem 352: Data Stream as Disjoint Intervals
- problem 502: IPO
- problem 895: Maximum Frequency Stack
- problem 982: Triples with Bitwise AND Equal To Zero
- problem 995: Minimum Number of K Consecutive Bit Flips
- problem 996: Number of Squareful Arrays
- problem 2136: Earliest Possible Day of Full Bloom
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality