Ransom Note

Difficulty: Easy | Acceptance: 65.90% | Paid: No Topics: Hash Table, String, Counting

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.

• Examples
• Constraints
• Hash Map Counting
• Array Counting
• Sorting Approach
• String Manipulation

Examples

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 <= 10⁵
ransomNote and magazine consist of lowercase English letters.

Hash Map Counting

Intuition Count the frequency of each character in magazine using a hash map, then verify ransomNote can be formed by checking and decrementing these counts.

Steps

• Create a hash map to count character frequencies in magazine
• Iterate through ransomNote, checking if each character exists with sufficient count
• Decrement count for each used character
• Return false if any character is missing or count is zero

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        from collections import Counter
        
        magazine_count = Counter(magazine)
        
        for char in ransomNote:
            if magazine_count[char] <= 0:
                return False
            magazine_count[char] -= 1
        
        return True

Complexity

• Time: O(m + n) where m and n are lengths of ransomNote and magazine
• Space: O(k) where k is the number of unique characters
• Notes: Most efficient for general character sets

Array Counting

Intuition Since the input only contains lowercase English letters, we can use a fixed-size array of 26 integers instead of a hash map for better performance.

Steps

• Initialize an array of size 26 with zeros
• Count each character in magazine by incrementing the corresponding index
• Iterate through ransomNote, decrementing counts and checking for availability
• Return false if any character count becomes negative

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:
            idx = ord(c) - ord('a')
            if count[idx] <= 0:
                return False
            count[idx] -= 1
        
        return True

Complexity

• Time: O(m + n) where m and n are lengths of ransomNote and magazine
• Space: O(1) fixed array of 26 integers
• Notes: Optimal for lowercase English letters only

Sorting Approach

Intuition Sort both strings and use two pointers to match characters, similar to the merge step in merge sort.

Steps

• Convert both strings to character arrays and sort them
• Use two pointers to traverse both sorted arrays
• If characters match, advance both pointers
• If magazine character is smaller, advance magazine pointer
• If ransomNote character is smaller, return false
• Return true if all ransomNote characters are matched

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ransom_sorted = sorted(ransomNote)
        magazine_sorted = sorted(magazine)
        
        i = j = 0
        
        while i < len(ransom_sorted) and j < len(magazine_sorted):
            if ransom_sorted[i] == magazine_sorted[j]:
                i += 1
                j += 1
            elif ransom_sorted[i] < magazine_sorted[j]:
                return False
            else:
                j += 1
        
        return i == len(ransom_sorted)

Complexity

• Time: O(m log m + n log n) due to sorting
• Space: O(m + n) for storing sorted arrays
• Notes: Less efficient than counting but demonstrates two-pointer technique

String Manipulation

Intuition For each character in ransomNote, try to find and remove it from magazine. If any character cannot be found, return false.

Steps

• Convert magazine to a mutable data structure (array or list)
• For each character in ransomNote
• Search for the character in magazine
• If found, remove it; if not found, return false
• Return true if all characters are found

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magazine_list = list(magazine)
        
        for c in ransomNote:
            if c in magazine_list:
                magazine_list.remove(c)
            else:
                return False
        
        return True

Complexity

• Time: O(m × n) in worst case due to linear search and removal
• Space: O(m) for storing magazine as mutable structure
• Notes: Simple but inefficient for large inputs