Problem 383

Abstract / Summary

Check if a ransom note can be made from letters in a magazine using each letter no more times than it appears in the magazine.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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;
    }
};
18 lines | 374 bytes | submitted August 9, 2023 | GitHub   tab size 4

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 66% (3+ million submissions).

Typical patterns to solve this problem:
  • Counting
  • Hash Table
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 8.41 | σ = 0.83

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
47 links | 32 authors | 12 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

2 similar problems

Solved On The Same Day

9 easy 2 medium 16 hard
28 solutions   August 9, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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