Solutions

1. Brute Force

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magazine = list(magazine)

        for c in ransomNote:
            if c not in magazine:
                return False
            else:
                magazine.remove(c)
        
        return True

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ and $n$ are the lengths of the strings $ransomNote$ and $magazine$ , respectively.

2. Count Frequency

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        countR = Counter(ransomNote)
        countM = Counter(magazine)

        for c in countR:
            if countM[c] < countR[c]:
                return False

        return True

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(1)$ since we have at most $26$ different characters.

Where $m$ and $n$ are the lengths of the strings $ransomNote$ and $magazine$ , respectively.

3. Count Frequency (Optimal)

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        count = [0] * 26
        for c in magazine:
            count[ord(c) - ord('a')] += 1

        for c in ransomNote:
            count[ord(c) - ord('a')] -= 1
            if count[ord(c) - ord('a')] < 0:
                return False

        return True

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(1)$ since we have at most $26$ different characters.

Where $m$ and $n$ are the lengths of the strings $ransomNote$ and $magazine$ , respectively.