DSA problem
Ransom Note
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
This means that for every distinct character, the number of times it appears in ransomNote must not exceed the number of times it appears in magazine. A clean way to check this is to count the character frequencies of magazine in a hash map and then decrement those counts as you scan ransomNote.
Examples
Example 1
Input:
ransomNote = "a", magazine = "b"Output:
falseExplanation: The note needs an a but the magazine only provides a b, so it cannot be constructed.
Example 2
Input:
ransomNote = "aa", magazine = "ab"Output:
falseExplanation: The note needs two a characters, but the magazine supplies only one, so construction fails.
Example 3
Input:
ransomNote = "aa", magazine = "aab"Output:
trueExplanation: The magazine has two a characters, which is exactly enough to cover the note. The leftover b is unused.
Constraints
- 1 <= ransomNote.length, magazine.length <= 10^5
- ransomNote and magazine consist of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.