Problem Definition

LeetCode Link:

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.

Thought Process

At first glance, this problem may remind you of checking if one string is an anagram of another. However, the task here is slightly different: we only need to verify that magazine provides enough characters to cover all characters required by ransomNote. We don’t need both ways, just one direction: every character count needed by ransomNote must be satisfied by magazine.

Key Insight

  • Since we only deal with lowercase letters, we can leverage a simple frequency array of length 26, or use dictionaries, collections.Counter, or defaultdict to store character frequencies.
  • Compare frequencies: if any character in ransomNote appears more times than it does in magazine, return false.
  • Otherwise, return true.

Complexity Considerations

  • Time Complexity: We’ll at least need to count the characters in both strings. This is O(m + n) where m = length of ransomNote and n = length of magazine.
  • Space Complexity: O(1) or O(k) where k is the character set size (26 for lowercase letters). If using dictionaries, it’s still effectively O(1) since the character set is fixed and finite.

Solution 1: Using Arrays as Frequency Counters

This approach uses two arrays of length 26—one for ransomNote and one for magazine—then compares frequencies.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ransom_count = [0] * 26
        magazine_count = [0] * 26

        for c in ransomNote:
            ransom_count[ord(c) - ord('a')] += 1

        for c in magazine:
            magazine_count[ord(c) - ord('a')] += 1

        # Check if magazine_count covers ransom_count for all characters
        return all(ransom_count[i] <= magazine_count[i] for i in range(26))

Step-by-Step:

  1. Initialize two lists of length 26 to zero, ransom_count and magazine_count.
  2. Count occurrences of each character in ransomNote and magazine.
  3. Compare counts: for every character (from a to z), ensure magazine has at least as many occurrences as ransomNote needs.
  4. Return true if all characters are covered, otherwise false.

Complexity:

  • Time Complexity: O(m + n)
  • Space Complexity: O(1)

Solution 2: Using collections.defaultdict

Using a defaultdict(int) simplifies the counting logic.

from collections import defaultdict

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

        for ch in magazine:
            char_count[ch] += 1

        for ch in ransomNote:
            if char_count[ch] <= 0:
                return False
            char_count[ch] -= 1

        return True

Step-by-Step:

  1. Build a frequency dictionary for magazine.
  2. For each character in ransomNote, decrement the count in char_count.
  3. If at any point a required character’s count would drop below 0, return false.
  4. If we finish without issues, return true.

Complexity:

  • Time Complexity: O(m + n)
  • Space Complexity: O(1) (since only lowercase letters)

Solution 3: Using a Dictionary with get()

Similar to the defaultdict method, but uses a normal dictionary with get().

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

        for c in ransomNote:
            if counts.get(c, 0) == 0:
                return False
            counts[c] -= 1

        return True

Step-by-Step:

  • Count frequencies in magazine using dict.get().
  • Iterate over ransomNote to ensure availability.
  • If shortage is found, return false; otherwise, true.

Complexity:

  • Time Complexity: O(m + n)
  • Space Complexity: O(1)

Solution 4: Using collections.Counter

Counter directly provides frequency counts and simplifies subtraction operations.

from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # If ransomNote requires characters that magazine doesn't have enough of, subtraction will show that.
        return not (Counter(ransomNote) - Counter(magazine))

Step-by-Step:

  1. Create Counter for ransomNote and magazine.
  2. Counter(ransomNote) - Counter(magazine) will remove counts from ransomNote's counter that appear in magazine.
  3. If after this subtraction there’s anything left, that means magazine didn’t have enough characters, so return false.
  4. If empty, return true.

Complexity:

  • Time Complexity: O(m + n)
  • Space Complexity: O(1)

Solution 5: Using count() Method on Strings

A more straightforward (but less efficient) Pythonic approach is to check counts character by character.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        return all(ransomNote.count(c) <= magazine.count(c) for c in set(ransomNote))

or

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        for char in ransomNote:
            if ransomNote.count(char) > magazine.count(char):
                return False
        return True

Step-by-Step:

  1. For each unique character in ransomNote, compare the counts in ransomNote and magazine.
  2. If ever ransomNote needs more than magazine can supply, return false.
  3. Otherwise, true.

Complexity:

  • Time Complexity: Potentially O(m*n) due to repeated counting operations for each unique character.
  • Space Complexity: O(1)

Key Takeaways

  • Frequency Counting is Key: Using arrays, dictionaries, or Counter is the most direct approach.
  • Array vs. Dictionary vs. Counter:
    • Arrays are very efficient for fixed character sets (O(1) space, no hashing overhead).
    • Counter is concise and clean, a good Pythonic solution.
    • Dictionaries and defaultdict offer flexible and still efficient implementations.
  • Avoid Repeated count() Calls for Performance: While straightforward, count() in a loop can degrade performance.