💵383. Ransom Note

Easy | Grind 75 | September 13rd Tuesday, 2022

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.

Constraints:

• 1 <= ransomNote.length, magazine.length <= 10^5

• ransomNote and magazine consist of lowercase English letters.

Example 1

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2

Example 3

SOLUTION

We begin by building a dictionary, magazine_dict, that stores the frequency of each character that appears in the magazine variable. We then traverse through the characters in the ransomNote and check if each character exists in the magazine_dict. For the ransom note construction to be successful, we know that every character in the ransomNote must be present in the magazine_dict. While traversing through the ransom note string, when we encounter a character that is present in the magazine_dict, we decrement the count of that character in the magazine_dict by 1. This is because we can use each letter only once. If we can't construct the ransom note, we will eventually encounter a character during the traversal that is not present in the magazine_dict.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # magazine length need to be longer than ransomNote
        if len(ransomNote) > len(magazine): 
            return False
        
        # make a dictionary with letter frequency of magazine
        magazine_dict = Counter(magazine)
        
        # iterate through every ransomnote character
        for char in ransomNote: 
            # if a ransomnote charcter is not in magazine, we know you cannot construct the note
            if char not in magazine_dict: 
                return False
            
            # everytime we see a charcter present, decrement the frequency count. 
            magazine_dict[char] -= 1
            # need to remove the key if the value is 0
            if magazine_dict[char] == 0: 
                del magazine_dict[char]
        
        return True

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the length of the magazine string. We build the magazine string into a dictionary which has a runtime of O(n). Also, given that you can only use each character once, you need to have the length of the magazine string either longer or equal to the lenght of ransomNote.

SPACE: O(n) where n is the length of the magazine string. We build the magazine_dict which in the worst case will take up n space.