Leetcode Problem Statement

Description

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:

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

Constraints

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote and magazine consist of lowercase English letters.

Key Insights

This is basically an inventory problem. If the demand for all required letters in ransomNote does not exceed the supply of letters in magazine, the function returns True. Otherwise, we return False.

In Python we can use collections.Counter to create hash maps that map items to frequencies. If an item is not present in a Counter hash map, the [] operator will return 0. If you would rather use *.get(), make sure to set the not found condition to 0. i.e. *.get(key, 0).

This problem is very simple to solve using Python’s Counter data structure. We create one hash map for ransomNote and one for magazine and initialize them with their respective strings. If we pass a string into the Counter constructor, it will return an item-frequency hash map for each unique letter. Once we have these two hash maps, we loop over the keys in the note hash map and check if we have enough letters in the magazine hash map. If we find a case where we end up overdrawn, we return False. If we don’t find any shortfalls, we return True at the end.

Python Solution

from collections import Counter
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        """
            T: O(R + M) -> O(N)
            S: O(R + M) -> O(N)
        """
        # Create item-value frequency hash maps
        note_mp = Counter(ransomNote)
        magz_mp = Counter(magazine)

        # Loop through the ransomNote hash map and check if we
        # have enough letters in the magazine hash map. If a debit
        # every results in a negative balance, we don't have sufficient
        # supply and we need to return False.
        for letter in note_mp:
            if magz_mp[letter] - note_mp[letter] < 0:
                return False
        
        # We made it! Return True!
        return True