Problem Statement
Given two strings, one representing a ransom note and the other representing the available letters from a magazine, determine if it's possible to construct the ransom note using only the letters from the magazine. Each letter from the magazine can be used only once.
Examples:
-
Example 1:
- Input: Ransom Note = "hello", Magazine = "hellworld"
- Expected Output: true
- Justification: The word "hello" can be constructed from the letters in "hellworld".
-
Example 2:
- Input: Ransom Note = "notes", Magazine = "stoned"
- Expected Output: true
- Justification: The word "notes" can be fully constructed from "stoned" from its first 5 letters.
-
Example 3:
- Input: Ransom Note = "apple", Magazine = "pale"
- Expected Output: false
- Justification: The word "apple" cannot be constructed from "pale" as we are missing one 'p'.
Constraints:
- 1 <= ransomNote.length, magazine.length <= 10<sup>5</sup>
- ransomNote and magazine consist of lowercase English letters.
Why this is a Hash Maps problem
| What the question says | The signal it matches |
|---|---|
| "determine if it's possible to construct the ransom note using only the letters from the magazine" | two inputs are compared as collections rather than sequences |
| "Each letter from the magazine can be used only once" | supply is limited, so both sides must be counted |
| searching the magazine for each letter of the note in turn | your first idea is a nested loop that recounts the same thing |
Counting the supply and checking the demand against it is the count and compare variant.
The closest alternative. A set is the wrong structure here, and it is worth knowing why. Membership alone says the letter exists somewhere. It cannot say whether there are two of them.
The single sentence limiting each letter to one use is what makes counts necessary. This is Maximum Number of Balloons asking a yes or no instead of how many.
Solution
To solve this problem, we will utilize a hashmap to keep track of the frequency of each character in the magazine. First, we iterate through the magazine, updating the hashmap with the count of each character. Then, we go through the ransom note. For each character in the note, we check if it exists in the hashmap and if its count is greater than zero. If it is, we decrease the count in the hashmap, indicating that we've used that letter. If at any point we find a character in the note that isn't available in sufficient quantity in the magazine, we return false. If we successfully go through the entire note without this issue, we return true, indicating the note can be constructed from the magazine.
-
Populate Frequency Map: Traverse the magazine string and populate a hashmap with the frequency of each character.
-
Check Feasibility: Traverse the ransom note string. For each character, check its frequency in the hashmap. If the character is not present or its frequency is zero, return false. Otherwise, decrement the frequency of the character in the hashmap.
-
Return Result: If we successfully traverse the ransom note without returning false, then it's possible to construct the ransom note from the magazine. Return true.
Using a hashmap allows for efficient storage and retrieval of character frequencies, ensuring that we can determine the feasibility of constructing the ransom note in linear time.
Algorithm Walkthrough
One walk over the magazine fills the map of what is available. The magazine is never read again. From here the map IS the supply. Spending a letter means lowering a count in it.
1 of 8
Code
Here is the code for this algorithm:
Complexity Analysis
Time Complexity: The algorithm traverses both the ransom note and the magazine once, making the time complexity O(n + m), where n is the length of the ransom note and m is the length of the magazine.
Space Complexity: The space complexity is determined by the hashmap, which in the worst case will have an entry for each unique character in the magazine. However, since the English alphabet has a fixed number of characters, the space complexity is O(1).
.....
.....
.....