# Ransom Note

## Problem

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MR14Aiz_WIQ0VurIfaV%2F-MR14o8NRtDz7vQdPPm9%2FScreen%20Shot%202021-01-14%20at%2011.10.11%20AM.png?alt=media\&token=4b88e06c-68ea-4737-8914-e87e318e415b)

### Thought Process

* Count the number of distinct characters appearing in the note 

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MR14Aiz_WIQ0VurIfaV%2F-MR158w3H04g7WGmV9w1%2FIMG_48535243B7F7-1.jpeg?alt=media\&token=17f07bde-3a52-4809-be26-bc829a708e83)

## Solution

```
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        dic = {}
        
        for letter in ransomNote:
            if letter not in dic:
                dic[letter] = 0
            dic[letter]+=1
        
        for i in magazine:
            if i in dic:
                dic[i]-=1
                if dic[i] == 0:
                    del dic[i]
        if len(dic) == 0:
            return True
        else:
            return False
                
```

## Time Complexity

* **Time:** O(n)
* **Space:** O(1) because hash set is bounded by 26 characters