notes/OJ notes/pages/Leetcode Ransom-Note.md

# Leetcode Ransom-Note

#### 2022-06-14 13:19

---

##### Algorithms:

#algorithm #hash_table

##### Data structures:

#DS #string #array

##### Difficulty:

#leetcode #coding_problem #difficulty_easy

##### Related topics:

##### Links:

- [Link to problem](https://leetcode.com/problems/ransom-note/)

---

### Problem

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:**

```markdown
**Input:** s = "leetcode"
**Output:** 0
```

**Example 2:**

```markdown
**Input:** s = "loveleetcode"
**Output:** 2
```

**Example 3:**

```markdown
**Input:** s = "aabb"
**Output:** -1
```

#### Constraints

**Constraints:**

- `1 <= s.length <= 105`
- `s` consists of only lowercase English letters.

### Thoughts

Super simple hash map, similar to [[Leetcode First-Unique-Character-In-a-String]]

### Solution

O(m + n)

```cpp
class Solution {
public:
  bool canConstruct(string ransomNote, string magazine) {
    // hashmap, O(m + n)
    int hashMap[26] = {};

    for (char c : magazine) {
      hashMap[c - 'a']++;
    }

    for (char c : ransomNote) {
      if (hashMap[c - 'a']-- == 0)
        return false;
    }
    return true;
  }
};
```