Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0383 - Ransom Note
    0383 - Ransom Note
    0383 - Ransom Note
    0383 - Ransom Note

    0383 - Ransom Note

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/ransom-note/

    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)TimeComplexity: O(n + m)TimeComplexity:O(n+m)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    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)TimeComplexity: O(n + m)TimeComplexity:O(n+m)
    SpaceComplexity:O(1)SpaceComplexity: O(1)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()

    """ 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()