LeetCode 383: Ransom Note Solution in Python – A Step-by-Step Guide

What Is LeetCode 383: Ransom Note?

LeetCode 383: Ransom Note gives you two strings: a ransomNote (the note to construct) and a magazine (the available letters). Your task is to determine if you can build the ransom note using only the characters from the magazine, where each character can be used at most once. It’s a problem that tests your ability to compare character frequencies efficiently!

Problem Statement

• Input:
• ransomNote: String representing the note to construct.
• magazine: String representing available letters.
• Output: Boolean - True if ransomNote can be constructed, False otherwise.
• Rules:
• Each character in magazine can be used only once.
• Case-sensitive (e.g., 'a' ≠ 'A').

Constraints

• 1 <= ransomNote.length, magazine.length <= 10⁵
• Both strings contain lowercase English letters.

Examples

• Input: ransomNote = "a", magazine = "b"
• Output: False
• No 'a' in magazine.
• Input: ransomNote = "aa", magazine = "ab"
• Output: False
• Only one 'a' in magazine, need two.
• Input: ransomNote = "aa", magazine = "aab"
• Output: True
• Two 'a’s and one 'b' available, can make "aa".

These show the letter-matching game—let’s solve it!

Understanding the Problem: Constructing the Note

To tackle LeetCode 383 in Python, we need to: 1. Check if every character in ransomNote exists in magazine with sufficient frequency. 2. Ensure each magazine character is used at most once. 3. Compare efficiently given the string lengths.

A naive approach might check each character repeatedly, but that’s slow. We’ll use:

• Best Solution: Hash map—O(n + m) time, O(1) space (fixed alphabet)—fast and optimal.
• Alternative Solution: Sorting—O(n log n) time, O(1) space—intuitive but slower.

Let’s optimize with the best solution!

Best Solution: Hash Map

Why This Is the Best Solution

The hash map approach runs in O(n + m) time (n is ransomNote length, m is magazine length) by counting character frequencies in the magazine once, then checking if the ransom note’s needs are met. It’s the most efficient—using O(1) extra space (26 lowercase letters) and avoiding sorting for linear performance!

How It Works

Think of it like a letter inventory:

• Hash Map: Count frequencies of characters in magazine.
• Check: For each character in ransomNote, subtract from map, ensure count ≥ 0.
• Result: True if all counts stay non-negative, False if any go below 0.

It’s like checking your letter stock against the note’s demand!

Step-by-Step Example

For ransomNote = "aa", magazine = "aab":

• Init: Map = {}.
• Count Magazine:
• 'a': 2, 'b': 1, Map = {'a': 2, 'b': 1}.
• Check Ransom:
• 'a': 2 → 1 (ok).
• 'a': 1 → 0 (ok).
• Result: All ≥ 0, return True.

For ransomNote = "aa", magazine = "ab":

• Count: Map = {'a': 1, 'b': 1}.
• Check:
• 'a': 1 → 0 (ok).
• 'a': 0 → -1 (not enough).
• Result: False.

For ransomNote = "a", magazine = "b":

• Count: Map = {'b': 1}.
• Check:
• 'a': 0 (not present).
• Result: False.

Code with Explanation

Here’s the Python code using a hash map:

Copy codeclass Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # Hash map for character frequencies (26 lowercase letters)
        char_count = {}

        # Count frequencies in magazine
        for char in magazine:
            char_count[char] = char_count.get(char, 0) + 1

        # Check if ransomNote can be constructed
        for char in ransomNote:
            if char not in char_count or char_count[char] == 0:
                return False
            char_count[char] -= 1

        return True

Explanation

• Line 4: char_count: Dictionary for character counts.
• Lines 6-7: Count each character in magazine—O(m).
• Lines 9-13: Check ransomNote:
• If char not in map or count = 0, return False.
• Decrement count—O(n).
• Line 15: Return True if all chars satisfied.
• Time: O(n + m)—linear pass over both strings.
• Space: O(1)—fixed 26-letter alphabet.

This is like a letter checker—quick and precise!

Alternative Solution: Sorting

Why an Alternative Approach?

The sorting solution runs in O(n log n + m log m) time by sorting both strings and comparing them sequentially. It’s less efficient—great for understanding a comparison-based approach, though slower and unnecessary given the hash map’s simplicity!

How It Works

• Sort: Sort both ransomNote and magazine.
• Compare: Traverse both, ensuring magazine has enough of each character.
• Result: True if magazine covers all, False if it runs out.

Step-by-Step Example

For ransomNote = "aa", magazine = "aab":

• Sort: ransomNote = "aa", magazine = "aab".
• Compare:
• i=0: 'a' = 'a', ransom_idx=1, mag_idx=1.
• i=1: 'a' = 'a', ransom_idx=2, mag_idx=2.
• ransomNote done, return True.

For ransomNote = "aa", magazine = "ab":

• Sort: ransomNote = "aa", magazine = "ab".
• Compare:
• i=0: 'a' = 'a', ransom_idx=1, mag_idx=1.
• i=1: 'a' < 'b', mag_idx=2 (out), return False.

Code with Explanation

Copy codeclass Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # Sort both strings
        ransom = sorted(ransomNote)
        mag = sorted(magazine)

        # Compare sorted strings
        ransom_idx = mag_idx = 0
        while ransom_idx < len(ransom) and mag_idx < len(mag):
            if ransom[ransom_idx] == mag[mag_idx]:
                ransom_idx += 1
                mag_idx += 1
            elif ransom[ransom_idx] > mag[mag_idx]:
                mag_idx += 1
            else:
                return False

        # Check if all ransom chars were matched
        return ransom_idx == len(ransom)

Explanation

• Lines 4-5: Sort both strings—O(n log n + m log m).
• Lines 7-15: Two-pointer comparison:
• If chars match, move both pointers.
• If ransom char > mag char, move mag pointer.
• If ransom char < mag char, mag lacks char, return False.
• Line 17: True if all ransom chars used—O(n + m).
• Time: O(n log n + m log m)—sorting dominates.
• Space: O(1)—in-place sorting (or O(n + m) if new arrays).

It’s a sorted letter matcher—intuitive but slower!

Comparing the Two Solutions

• Hash Map (Best):
• Time: O(n + m)—linear.
• Space: O(1)—fixed alphabet.
• Pros: Fast, space-efficient.
• Cons: Slightly more code.
• Sorting (Alternative):
• Time: O(n log n + m log m)—sorting.
• Space: O(1)—minimal.
• Pros: Simple comparison.
• Cons: Slower due to sorting.

Hash map wins for speed and efficiency!

Additional Examples and Edge Cases

• ransomNote="", magazine="a": True (empty note).
• ransomNote="a", magazine="": False (no letters).
• Long strings: Hash map scales better.

Both handle these, hash map is faster.

Complexity Breakdown

• Hash Map:
• Time: O(n + m).
• Space: O(1).
• Sorting:
• Time: O(n log n + m log m).
• Space: O(1).

Hash map excels for performance.

Key Takeaways

• Hash Map: Count and check—fast and lean!
• Sorting: Order and compare—clear but slow!
• Strings: Frequency drives solutions.
• Python Tip: Dicts rock—see [Python Basics](/python/basics).

Final Thoughts: Crack That Note

LeetCode 383: Ransom Note in Python is a string-matching challenge. Hash map is the efficiency champ, while sorting offers a straightforward alternative. Want more? Try LeetCode 242: Valid Anagram or LeetCode 438: Find All Anagrams in a String. Ready to sleuth? Visit Solve LeetCode 383 on LeetCode and construct that note today!