Ransom Note

The problem description can be found in LeetCode.

Approach

Usually, for problems that involve strings, we might need to use a counter dictionary for the characters.

In order to build our ransom note we need a certain number of characters, and all of them must be in the magazine. So we have to count such characters and check if we have enough of them in the magazine.

Since our alphabet is limited to lowercase English letters, we can count them by using a static list of 26 elements as we did for the Valid Anagram problem.

Once we have the two counters, we can simply iterate over the one of the ransom note and check if the magazine counter has enough occurrences for the i-th character:

from typing import List


class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(ransomNote) > len(magazine):
            return False

        rn_counter = self.get_chars_counter(ransomNote)
        m_counter = self.get_chars_counter(magazine)

        for i, occ in enumerate(rn_counter):
            if m_counter[i] < occ:
                return False

        return True

    def get_chars_counter(self, s: str) -> List[int]:
        m = [0] * 26

        for char in s:
            idx = ord(char) - ord("a")
            m[idx] += 1

        return m

This would take $O(n)$ time and $O(1)$ space, where $n$ is the length of the magazine string (which is greater than the size of the string ransomNote).

Even if this solution is accepted, there is a slightly better way to solve the issue.

In fact, for this kind of problems, sometimes we can build a single counter and then apply some logic to it to verify its properties. In this case, once we get the counter, we can simply iterate over the ransomNote string and subtract the i-th character to the counter. If the number of its occurrence is less than 0, it means that we do not have enough characters from the magazine, hence, we cannot build the ransom note.

Please, notice that in terms of $O$ notation, the complexity is the same compared to the previous approach. However, the code will be faster since we are going to run less instructions.

Solution

from typing import List


class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(ransomNote) > len(magazine):
            return False

        counter = self.get_chars_counter(magazine)

        for char in ransomNote:
            idx = self.get_idx_from_char(char)
            counter[idx] -= 1

            if counter[idx] < 0:
                return False

        return True

    def get_chars_counter(self, s: str) -> List[int]:
        m = [0] * 26

        for char in s:
            idx = self.get_idx_from_char(char)
            m[idx] += 1

        return m

    def get_idx_from_char(self, char: str) -> int:
        assert isinstance(char, str)
        assert len(char) == 1

        return ord(char) - ord("a")

Complexity

• Time: $O(n)$
• Space: $O(1)$

Where $n$ is the length of the magazine string.