383. Ransom Note

1. Description

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.

2. Example

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

3. Constraints

• You may assume that both strings contain only lowercase letters.

4. Solutions

n = magazine.size()
Time complexity: O(n)
Space complexity: O(1)

Hash Table

class Solution {
public:
    bool canConstruct(const string &ransomNote, const string &magazine) {
        if (ransomNote.size() > magazine.size()) {
            return false;
        }

        array<int, 26> letter_count;
        for (char letter : magazine) {
            ++letter_count[letter - 'a'];
        }
        for (char letter : ransomNote) {
            --letter_count[letter - 'a'];

            if (letter_count[letter - 'a'] < 0) {
                return false;
            }
        }

        return true;
    }
};