Ransom Note

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given a string magazine and a string ransomNote, determine whether the ransomNote can be made from the letters in magazine

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Each letter in magazine can only be used once
• Each letter in ransomNote must be in magazine
• We don't have to use all letters in magazine

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Hash Map
• Strings

Time & Space Complexity

• Time: $O(n+m)$ → Reason: Iterating through each input once
• Space: $O(1)$ → Reason: Storing count of letters (finite - 26)

Code

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        countOfLetters = {}
        for letter in magazine:
            countOfLetters[letter] = countOfLetters.get(letter, 0) + 1

        for letter in ransomNote:
            if letter not in countOfLetters or countOfLetters[letter] == 0:
                return False
            else:
                countOfLetters[letter] -= 1

        return True