Problem

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.

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.

Solution

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        # > Each letter in magazine can only be used once in ransomNote.
        # sounds like we need a set! Except if ransomNote has 'aa' we need to record both a's
        # For this we can use collections.Counter which is a fancy python dict
        # below we create a countes object of both ransomNote and the magazine
        # the counter counts how many times the chars appear, so if you do:
        # {"a": 3} - {"a": 1} it'll result in {"a": 2}
        return not collections.Counter(ransomNote) - collections.Counter(magazine)

If you can't use Collections you can instead use sets and count the elements:

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        for i in set(ransomNote):
            if ransomNote.count(i) > magazine.count(i):
                return False
        return True