Solution 1 - Hash Map (Counter)

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. Count the frequency of each character in magazine, then iterate through ransomNote and decrement counts. If any count goes below zero, return False.

TimeComplexity: O(n + m)

SpaceComplexity: O(1)

""" 0383.1 - Solution 1 - Hash Map (Counter) Approach """

#####################################################################################
# Imports
#####################################################################################
from collections import Counter

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        """Ransom Note Function"""
        mag_count = Counter(magazine)
        for char in ransomNote:
            if mag_count[char] <= 0:
                return False
            mag_count[char] -= 1
        return True


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().canConstruct("a", "b"))        # False
    print(Solution().canConstruct("aa", "ab"))       # False
    print(Solution().canConstruct("aa", "aab"))      # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Counter Subtraction

Use Python's Counter to count characters in both strings, then check if the ransom note's character counts are all satisfied by the magazine's counts using counter subtraction.

TimeComplexity: O(n + m)

SpaceComplexity: O(1)

""" 0383.2 - Solution 2 - Counter Subtraction Approach """

#####################################################################################
# Imports
#####################################################################################
from collections import Counter

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        """Ransom Note Function"""
        return not (Counter(ransomNote) - Counter(magazine))


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().canConstruct("a", "b"))        # False
    print(Solution().canConstruct("aa", "ab"))       # False
    print(Solution().canConstruct("aa", "aab"))      # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0383 - Ransom Note

Solution 1 - Hash Map (Counter)

Solution 2 - Counter Subtraction