## Leetcode Problem Statement#

### Description#

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`.

### Examples#

#### Example 1:#

``````Input: ransomNote = "a", magazine = "b"
Output: false
``````

#### Example 2:#

``````Input: ransomNote = "aa", magazine = "ab"
Output: false
``````

#### Example 3:#

``````Input: ransomNote = "aa", magazine = "aab"
Output: true
``````

### Constraints#

• `1 <= ransomNote.length`, `magazine.length <= 105`
• `ransomNote` and `magazine` consist of lowercase English letters.

## Key Insights#

This is basically an inventory problem. If the demand for all required `letters` in `ransomNote` does not exceed the supply of `letters` in `magazine`, the function returns `True`. Otherwise, we return `False`.

In Python we can use `collections.Counter` to create `hash maps` that map `items` to `frequencies`. If an `item` is not present in a `Counter` `hash map`, the `[]` operator will return `0`. If you would rather use `*.get()`, make sure to set the not found condition to `0`. i.e. `*.get(key, 0)`.

This problem is very simple to solve using Python’s `Counter` data structure. We create one hash map for `ransomNote` and one for `magazine` and initialize them with their respective strings. If we pass a string into the `Counter` constructor, it will return an item-frequency hash map for each unique letter. Once we have these two hash maps, we loop over the keys in the note hash map and check if we have enough `letters` in the `magazine` hash map. If we find a case where we end up overdrawn, we return `False`. If we don’t find any shortfalls, we return `True` at the end.

## Python Solution#

``````from collections import Counter
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
"""
T: O(R + M) -> O(N)
S: O(R + M) -> O(N)
"""
# Create item-value frequency hash maps
note_mp = Counter(ransomNote)
magz_mp = Counter(magazine)

# Loop through the ransomNote hash map and check if we
# have enough letters in the magazine hash map. If a debit
# every results in a negative balance, we don't have sufficient
# supply and we need to return False.
for letter in note_mp:
if magz_mp[letter] - note_mp[letter] < 0:
return False

# We made it! Return True!
return True
``````