Ransom Note

This classic string manipulation problem is a favorite question at companies like Google, Amazon, and Meta because it tests your understanding of character frequency counting and hash map optimization. While it appears simple on the surface, the fundamental concepts about efficiently tracking frequencies lays the groundwork for tackling more complex string-matching and anagram problems.

Problem statement

Given two strings ransomNote and magazine, determine whether ransomNote can be constructed using letters from the magazine. Return true if construction is possible, otherwise return false.

Constraints

• 1 <= ransomNote.length, magazine.length <= 10⁵
• ransomNote and magazine consist of lowercase English letters only.

Examples

Naive approach: Repeated linear search

A naive approach is to scan through the magazine for each character in the ransomNote. For every character needed, the algorithm searches linearly through the magazine to find a match, then marks it as used to prevent reuse. This continues until either all characters are found or a required character is unavailable.

This approach has a time complexity of O(N × M), where N is the length of the ransomNote and M is the length of the magazine. With both strings containing up to 10⁵ characters, this results in up to 10¹⁰ operations, exceeding typical time limits. The core inefficiency stems from treating this as a string matching problem when it’s fundamentally about counting character availability. If the ransomNote contains repeated letters, the entire magazine is scanned separately for each occurrence, creating unnecessary overlapping work.

Optimized approach using HashMap

The optimized approach is essentially the same idea (“find and consume letters from the magazine”), but instead of searching each time, it preprocesses the magazine once into an inventory of available letters. That hash map acts like a fast replacement for “scan and mark used”: each lookup tells you instantly whether a letter is available, and decrementing the count is the efficient version of marking a character as used.

Step-by-step algorithm

1. Create an empty hash map char_count = {}.
2. Iterate through each character c in magazine:
   1. If c exists in char_count,
      1. Increment its value by 1.
      2. If c doesn’t exist, set char_count[c] = 1 (where the key is the character and the value is its frequency count).
3. Iterate through each character c in ransomNote:
   1. If c is not in char_count or char_count[c] equals 0,
      1. Return False.
   2. Otherwise,
      1. Decrement char_count[c] by 1.
4. Return True if all characters are successfully processed.

To better understand the solution, let’s walk through the algorithm using the illustration below:

1 / 6

Python implementation

def canConstruct(ransomNote, magazine):
    """
    Input:
        ransomNote: The string we want to construct
        magazine: The string containing available letters
        
    Returns:
        True if ransomNote can be constructed, False otherwise
    """
    # Build frequency map of letters available in magazine
    char_count = {}
    for char in magazine:
        char_count[char] = char_count.get(char, 0) + 1
    
    # Try to "consume" each letter needed for ransom note
    for char in ransomNote:
        # If letter doesn't exist or count is 0, we can't construct the note
        if char not in char_count or char_count[char] == 0:
            return False
        # Decrement the available count
        char_count[char] -= 1
    return True


def main():
    
    test_cases = [
        ("aab", "baa"),
        ("abc", "aabbcc"),
        ("a", ""),
        ("leetcode", "loremipsumdolorsitamet"),
        ("zzz", "zz")
        
    ]
    
    for i, (ransom, mag) in enumerate(test_cases, 1):
        
        print(f"\n {i}:. \tInput: ")
        print(f" \t \tRansom Note: '{ransom} '")
        print(f" \t \tMagazine:    '{mag}' \n")
        print(f" \tOutput: {canConstruct(ransom, mag)}")
        print( "-"*75)


if __name__ == "__main__":
    main()

Time complexity

The time complexity of this algorithm is O(N + M) because:

• We make a single pass through the magazine string of length M to build the frequency map, which takes O(M) time.
• Then we make a single pass through the ransomNote string of length N, performing constant-time hash map lookups and updates for each character, which takes O(N) time.

Space complexity

The space complexity is O(k), where k is the number of distinct characters stored in char_count. Since the strings contain only lowercase English letters, k ≤ 26, so the extra space is effectively constant. Therefore, in this problem’s constraints, the space complexity is O(1).

Common pitfalls and interview tips

• The Empty String Edge Case: An empty ransom note ("") should always return true because we need zero letters to construct nothing. Some candidates add special-case handling, but the algorithm naturally handles it; the loop simply doesn’t execute.
• Magazine vs. Ransom Note Order: A common mistake is building the frequency map from the ransom note instead of the magazine. Remember that the magazine is our resource pool, and the ransom note is our shopping list. We count what we have (magazine), then check what we need (ransom note).
• Off-by-One with Decrementing: After checking if a character exists and has count > 0, make sure to decrement before checking the next character. Some candidates forget to decrement, leading to incorrect results when the same letter appears multiple times in the ransom note.