> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/strings/string-simulation/ransom-note.md).

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

![](/files/-MR14o8NRtDz7vQdPPm9)

### Thought Process

* Count the number of distinct characters appearing in the note 

![](/files/-MR158w3H04g7WGmV9w1)

## 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