NUHMAN.com

📘 Problem Statement

You are given two strings: ransomNote and magazine. You need to determine if you can construct the ransomNote using the characters from the magazine. Each letter in the magazine can only be used once in the ransom note.

Return true if you can construct the ransom note, otherwise return false.

📚 Example:

python

Input:
ransomNote = "a", magazine = "b"
Output: false

Input:
ransomNote = "aa", magazine = "aab"
Output: true

🧠 Key Insight

In this problem, we are essentially trying to check if every character in the ransom note has a corresponding character in the magazine with enough occurrences. This is a frequency counting problem where we can use a hashmap (or dictionary) to track the frequency of each character in the magazine and check if the ransom note can be constructed.

💡 Approach

1. Count the frequency of each character in both the ransomNote and the magazine.
2. Compare the frequency of each character in the ransom note with that in the magazine.
3. If for any character, the ransom note requires more characters than the magazine provides, return false.
4. If all characters in the ransom note can be constructed from the magazine, return true.

We can use a hashmap (dictionary) to store the frequency of each character in the magazine and then decrement the count for each character as we "use" it to form the ransom note.

🐍 Python Code

python

from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        """
        Check if the ransomNote can be constructed from the magazine.
        """
        # Count the frequency of characters in the ransomNote and magazine
        ransomNote_count = Counter(ransomNote)
        magazine_count = Counter(magazine)
        
        # Check if for each character in ransomNote, it is available in the magazine in required amount
        for char, count in ransomNote_count.items():
            if magazine_count[char] < count:
                return False
        return True

🔍 Step-by-Step Explanation

1. Count Character Frequencies

python

ransomNote_count = Counter(ransomNote)
magazine_count = Counter(magazine)

• We use the Counter class from Python's collections module to create dictionaries that store the frequency of each character in both the ransomNote and magazine strings.

2. Check Frequency for Each Character

python

for char, count in ransomNote_count.items():
    if magazine_count[char] < count:
        return False

• We loop through each character in the ransomNote and check if the magazine has enough occurrences of that character. If any character in the ransom note requires more instances than available in the magazine, we return false immediately.

3. Return True

python

return True

• If we complete the loop without returning false, it means all characters in the ransom note can be formed using characters from the magazine, and we return true.

💡 Example Walkthrough

Example 1:

python

Input:
ransomNote = "a", magazine = "b"
Output: false

• Step 1: ransomNote_count = Counter("a") → {'a': 1}
• Step 2: magazine_count = Counter("b") → {'b': 1}
• Step 3: We check if 'a' exists in the magazine. The magazine contains 'b', not 'a'. Hence, return false.

Example 2:

python

Input:
ransomNote = "aa", magazine = "aab"
Output: true

• Step 1: ransomNote_count = Counter("aa") → {'a': 2}
• Step 2: magazine_count = Counter("aab") → {'a': 2, 'b': 1}
• Step 3: The magazine contains exactly two 'a's, which is sufficient to form the ransom note. Hence, return true.

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(m + n)Space ComplexityO(m + n)

• Time Complexity:
• Counting the frequency of characters in both strings takes O(m) for the ransom note and O(n) for the magazine, where m and n are the lengths of the ransom note and the magazine, respectively.
• Checking the counts of each character in the ransom note against the magazine takes O(m) time.
• Hence, the total time complexity is O(m + n).
• Space Complexity:
• We use two Counter objects, each of size proportional to the number of distinct characters in the ransom note and the magazine. The space complexity is therefore O(m + n) in the worst case.

🧵 Final Thoughts

LeetCode 383 is an example of solving a string matching problem using frequency counting. The solution leverages Python's Counter class for efficient frequency calculation, which makes the solution both clean and fast. The problem also demonstrates how hashmaps can be used for tasks involving character counts, providing an optimal and scalable solution for real-world applications where string analysis is required.