Start learning free

LESSON 257 OF 410 · HASH TABLE

Ransom Note in O(n + m) Time Complexity using Python

Practice O(n + m) Read the full explanation

Given two strings ransomNote and magazine, return True if ransomNote can be constructed from magazine and False otherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

Input:  ransomNote = "aa", magazine = "abb"
Output:  False

Example 2:

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

Note:

Your algorithm should run in O(n + m) time and use O(Σ) extra space.


Hints:

Let's take the two examples given in the statement and solve them "by hand". In both examples, ransomNote consists of two 'a's. Which means we need to have at least two 'a's in magazine to be able to construct the solution. In the first example, we have only one 'a' in magazine and that's why we return False while in the second example, we have two of them, so that's why we return True. Pretty simple. Now what if ransomNote also contains letter 'b'? What property should be satisfied to return True? Take some small examples on paper and try to figure it out.

Let's take ransomNote = "abba". We need at least two 'a's and two 'b's in magazine to be able to construct the solution. First observation is that the order of letters in ransomNote is not important. The requirement is the same also for ransomNote = "aabb" or ransomNote = "abba". The same holds true for magazine. It doesn't matter if magazine = "aaabbb" or magazine = "ababab", both are good as the conditions are satisfied:
  • 'a' occurs in magazine at least the same number of times it does in ransomNote (3 >= 2)
  • 'b' occurs in magazine at least the same number of times it does in ransomNote (3 >= 2)
All these being said, can you figure out what condition should be satisfied to return True for the general case?

The condition is that for each letter of the alphabet (from 'a' to 'z'), the letter should appear in magazine at least the same number of times it does in ransomNote. So we need to separately count the number of occurrences of each letter in magazine and in ransomNote. How can we achieve this?

We have a data structure specially designed to do that: a frequency table, such as a Hash Map (or, since the letters are only 'a' to 'z', a 26-slot array). We can build two frequency tables:
  • one for ransomNote, where the entry for letter c is the number of occurrences of c in ransomNote
  • one for magazine, where the entry for letter c is the number of occurrences of c in magazine
How should we populate these tables?

Using a loop, we will go through every character c of ransomNote and increment the entry for c in its table. We will do the same for magazine. What should we do after we have populated these tables?

Using a loop, we should go through each character c of the alphabet (from 'a' to 'z') and check if the count of c in ransomNote is greater than its count in magazine. If so, we should return False. When this loop terminates, we can conclude that the solution is valid, so we can return True

STEP 1 OF 9
    Ctrl + Enter to check

    PYTHON · HASH TABLE

    Ransom Note in Python, explained

    Problem Definition

    The problem requires us to determine if we can construct the string ransomNote using the characters from the string magazine. Each character in magazine can only be used once.

    Input:

    • ransomNote: A string representing the ransom note.
    • magazine: A string representing the magazine text.

    Output:

    • Return true if ransomNote can be constructed from magazine, otherwise return false.

    Constraints:

    • Both strings consist of lowercase English letters.

    Example:

    Input: ransomNote = "aa", magazine = "abb"
Output: false

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

    Understanding the Problem

    The core challenge is to ensure that every character in ransomNote appears in magazine at least as many times as it does in ransomNote. This problem is significant in scenarios where resource allocation or availability needs to be checked.

    Common Pitfalls:

    • Assuming characters can be reused in magazine.
    • Not accounting for all characters in ransomNote.

    Approach

    To solve this problem, we can use a hash map (dictionary in Python) to count the occurrences of each character in both ransomNote and magazine. We then compare these counts to determine if the construction is possible.

    Naive Solution:

    A naive solution would involve iterating through each character in ransomNote and checking if it exists in magazine, removing it if found. This approach is not optimal as it involves multiple scans and deletions, leading to higher time complexity.

    Optimized Solution:

    We can optimize the solution by using two hash maps to store the frequency of each character in ransomNote and magazine. This allows us to perform the comparison in linear time.

    Algorithm

    1. Initialize two dictionaries to count the frequency of characters in ransomNote and magazine.
    2. Iterate through each character in ransomNote and populate the first dictionary.
    3. Iterate through each character in magazine and populate the second dictionary.
    4. For each character in the first dictionary, check if the count in magazine is at least as much as in ransomNote.
    5. If any character's count in magazine is less, return false.
    6. If all checks pass, return true.

    Code Implementation

    def can_construct(ransomNote: str, magazine: str) -> bool:
    # Initialize dictionaries to count character frequencies
    ransom_freq = {}
    magazine_freq = {}
    
    # Populate ransom_freq with characters from ransomNote
    for char in ransomNote:
        if char in ransom_freq:
            ransom_freq[char] += 1
        else:
            ransom_freq[char] = 1
    
    # Populate magazine_freq with characters from magazine
    for char in magazine:
        if char in magazine_freq:
            magazine_freq[char] += 1
        else:
            magazine_freq[char] = 1
    
    # Check if magazine contains enough characters for ransomNote
    for char in ransom_freq:
        if ransom_freq[char] > magazine_freq.get(char, 0):
            return False
    
    return True

# Example usage
print(can_construct("aa", "abb"))  # Output: False
print(can_construct("aa", "aab"))  # Output: True

    Complexity Analysis

    The time complexity of this solution is O(n + m), where n is the length of ransomNote and m is the length of magazine. This is because we iterate through both strings once to populate the frequency dictionaries.

    The space complexity is O(Σ), where Σ is the number of unique characters in the input strings. This is due to the storage required for the frequency dictionaries.

    Edge Cases

    • Empty ransomNote: Should return true as no characters are needed.
    • Empty magazine: Should return false if ransomNote is not empty.
    • Characters in ransomNote not present in magazine: Should return false.

    Testing

    To test the solution comprehensively, consider the following test cases:

    assert can_construct("", "") == True
assert can_construct("a", "") == False
assert can_construct("", "a") == True
assert can_construct("a", "a") == True
assert can_construct("aa", "aab") == True
assert can_construct("aa", "ab") == False

    Thinking and Problem-Solving Tips

    • Break down the problem into smaller parts and solve each part individually.
    • Use hash maps or dictionaries to efficiently count and compare frequencies.
    • Practice similar problems to improve your understanding of frequency counting and hash maps.

    Conclusion

    Understanding and solving the "Ransom Note" problem helps in developing skills related to frequency counting and efficient use of hash maps. This problem is a good exercise in optimizing solutions and understanding time and space complexity.

    Additional Resources

    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free