You get a ransom note and a magazine. Can the note be built from letters cut out of the magazine, using each letter at most once?
DSA Animator › DSA Revision › Arrays › Ransom Note
Remember: "can I build this" problems are letter counts. Add from the supply, subtract for the demand, and watch for negatives. The video solves Ransom Note (LeetCode 383, Easy) with the Frequency Count pattern from the Arrays topic, and you can replay every step in the interactive Ransom Note animation.
You get a ransom note and a magazine. Can the note be built from letters cut out of the magazine, using each letter at most once?
The note a a can be built from the magazine a a b, so the answer is true. But a a cannot be built from a b, because there is only one a.
Searching the magazine for each note letter, and removing it, is O of n times m. Counting letters is much faster.
Count how many of each letter the magazine has. Then go through the note, using up one count per letter. If any count would go below 0, the note is impossible.
The magazine a a b gives counts: a 2, b 1. The first a of the note uses one, so a is 1. The second a uses another, so a is 0. No count went negative, so the answer is true.
In code, fill an array of 26 counts from the magazine. For each note letter, decrease its count, and return false if it drops below 0. Otherwise return true, so it's O of n plus m time and O of 1 space.
Remember: "can I build this" problems are letter counts. Add from the supply, subtract for the demand, and watch for negatives.