Ransom Note
Easy · Arrays & Hashing · Hash Table · String · Counting
Problem
You are given two strings, ransomNote and magazine. You want to build the note by cutting letters out of the magazine, and each letter of magazine can be used at most once.
Return true if ransomNote can be built from the letters of magazine, and false otherwise.
Examples
Input: ransomNote = "meet", magazine = "temeptx" Output: true
The magazine supplies the m, both e's and the t.
Input: ransomNote = "zz", magazine = "zebra" Output: false
The magazine has only one z.
Input: ransomNote = "b", magazine = "a" Output: false
There is no b to cut out.
Constraints
- 1 <= len(ransomNote), len(magazine) <= 10^5
- ransomNote and magazine consist of lowercase English letters.
Approaches
- Baseline: cross letters off a copy — time O(n · m), space O(m)
Follow-up
What if the magazine is huge and many different notes are checked against it? Count the magazine once and keep the counts; each note then costs only its own length. The first use case below asks a version of exactly that.
Related problems
Start free on Cariara · Coding problems · System design studio
