383. Ransom Note

EasyHash TableStringCounting
Leetcode Link

Problem Description

The problem presents us with two strings: ransomNote and magazine. Our task is to determine if it's possible to construct the ransomNote string using the letters from the magazine string. There are certain rules to follow for this construction:

  • Each letter in the magazine can be used only once.
  • The order of the letters in the ransomNote does not have to match the order in the magazine.
  • If all letters in the ransomNote can be matched to letters in magazine, taking into account the frequency of each letter, then the output should be true.
  • Conversely, if there are any letters in the ransomNote which appear more times than they do in the magazine, or if there are any letters in the ransomNote that don't appear in the magazine at all, the output should be false.

Considering the above points, an immediate intuitive answer might seem complex since it implicitly involves tracking the count of each character in both ransomNote and magazine. The heart of the problem lies in efficiently checking the availability of each character needed to form the ransomNote.

Intuition

When considering the constraints of the problem, we naturally lean towards solutions that involve counting the frequency of each letter. The key, intuitive insight here is the realization that if magazine contains all the letters required by ransomNote in the necessary quantities, then we should be able to "use up" these letters from the magazine without any shortage.

To arrive at the solution, we think of keeping a tally of all the letters in magazine. A sensible way to achieve this is by using a hash table or a fixed-size array (since the alphabet is of fixed size - 26 letters for English). For each character in magazine, we increase its count in our tally. We then decrement these counts for each letter in ransomNote. If at any point the count for a particular letter drops below zero, it means ransomNote requires more of that letter than magazine can supply, and hence, we cannot construct ransomNote with the given magazine. The final result hinges on this check. If the entire ransomNote is processed without any count going negative, it's possible to create ransomNote from magazine; otherwise, it is not.

Solution Approach

The provided solution approach utilizes a hash table data structure, more specifically a Counter, which comes from Python's standard library collections. The hash table is particularly suited for this problem as it allows us to efficiently keep track of the counts of individual characters.

Here is how the algorithm works step by step:

  1. First, we initialize the hash table by passing the magazine string to the Counter, which will count the occurrences of each character in magazine and store them in the cnt hash table.

  2. Next, we iterate through each character c in the ransomNote string. For each such character, we perform two operations:

    • We decrement the count of the character c in the hash table cnt.
    • We check if the count of the character c falls below 0 after the decrement. If it does, it indicates that magazine does not have enough occurrences of character c to match the requirements of ransomNote, and we return False.
  3. If we can iterate through all characters in ransomNote without the count of any character falling below 0, it implies that magazine contains sufficient characters to construct ransomNote. Therefore, we return True.

Using the hash table for frequency counting is efficient as both insertion and lookup operations are on average O(1) complexity. The solution's overall time complexity is O(n+m), where n is the length of ransomNote and m is the length of magazine, since we have to iterate over both strings entirely. The space complexity is O(1) - even though we are using extra space for the hash table, it's size depends on the size of the character set (which is fixed), not the size of the input. In this case, it is the 26 letters of the English alphabet, hence it is a constant space overhead.

Using a Counter is particularly nifty here because it wraps up the necessary operations of initializing the frequency counts from magazine, decrementing with each character from ransomNote, and performing the check for a negative amount in a concise and readable manner. This indicates a great example of choosing the right data structures to simplify the implementation of an algorithm.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Imagine the ransomNote is "aabbcc" and the magazine is "abccbaac". We want to know if we can construct the ransom note using the letters from the magazine.

Following the solution approach:

  1. We initialize the hash table cnt using Counter with the magazine string:

    1cnt = Counter("abccbaac") 
    2// The counter will have counts for letters as follows: {'a': 3, 'b': 2, 'c': 3}
  2. Next, we iterate through each character c in the ransomNote string "aabbcc" and update the hash table cnt:

    • We take the first character 'a' from the ransomNote:
      • Decrement the count of 'a' in cnt by 1: Counter({'a': 2, 'b': 2, 'c': 3})
      • Count is not below 0, we move to the next character.
    • We take the second character 'a':
      • Decrement the count again: Counter({'a': 1, 'b': 2, 'c': 3})
      • Count is not below 0, we move to the next character.
    • We take the first 'b':
      • Decrement the count of 'b': Counter({'a': 1, 'b': 1, 'c': 3})
      • Count is not below 0, we move on.
    • We take the second 'b':
      • Decrement the count: Counter({'a': 1, 'b': 0, 'c': 3})
      • Count is not below 0, so we continue.
    • We take the first 'c':
      • Decrement the count of 'c': Counter({'a': 1, 'b': 0, 'c': 2})
      • Count is not below 0, move to the next character.
    • We take the second 'c':
      • Decrement the count: Counter({'a': 1, 'b': 0, 'c': 1})
      • Count is not below 0.
  3. Since we have gone through all the characters in ransomNote without any count falling below 0, we can conclude that it's possible to construct ransomNote from the magazine.

Thus, the result for the example would be True.

This example illustrates how the solution approach uses Counter to efficiently manage character counts from the magazine, and then check against the characters required to form the ransom note.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def canConstruct(self, ransom_note: str, magazine: str) -> bool:
5        # Create a counter object for all characters in the magazine
6        char_count = Counter(magazine)
7      
8        # Check each character in the ransom note
9        for char in ransom_note:
10            # Decrement the count for this character in the counter
11            char_count[char] -= 1
12          
13            # If count goes below zero, we cannot construct the note from the magazine
14            if char_count[char] < 0:
15                return False
16      
17        # If we haven't returned False, we can construct the ransom note
18        return True
19
1class Solution {
2
3    public boolean canConstruct(String ransomNote, String magazine) {
4        // Array to count occurrences of each letter in the magazine.
5        int[] letterCounts = new int[26];
6      
7        // Populate the letterCounts array with the count of each character in the magazine.
8        for (int i = 0; i < magazine.length(); i++) {
9            // Increment the count of the current character.
10            letterCounts[magazine.charAt(i) - 'a']++;
11        }
12      
13        // Check if the ransom note can be constructed using the letters in the magazine.
14        for (int i = 0; i < ransomNote.length(); i++) {
15            // Decrement the count of the current character, as it is used in the ransom note.
16            if (--letterCounts[ransomNote.charAt(i) - 'a'] < 0) {
17                // If any letter in the ransom note is in deficit, return false.
18                return false;
19            }
20        }
21      
22        // If all letters are accounted for, return true.
23        return true;
24    }
25}
26
1class Solution {
2public:
3    // Function to check if ransomNote can be constructed from magazine
4    bool canConstruct(string ransomNote, string magazine) {
5        // Create a frequency array for each letter in the alphabet
6        int letterCount[26] = {};
7
8        // Iterate through each character in the magazine
9        for (char& letter : magazine) {
10            // Increase the count for the corresponding letter
11            // 'a' maps to index 0, 'b' to 1, ..., 'z' to 25
12            ++letterCount[letter - 'a'];
13        }
14
15        // Iterate through each character in the ransomNote
16        for (char& letter : ransomNote) {
17            // Decrease the count for the corresponding letter
18            if (--letterCount[letter - 'a'] < 0) {
19                // If the count goes negative, magazine doesn't have enough of this letter
20                return false;
21            }
22        }
23
24        // If we've gone through the entire note without issues, the note can be constructed
25        return true;
26    }
27};
28
1function canConstruct(ransomNote: string, magazine: string): boolean {
2    // Initialize an array to keep track of the frequency of each letter in the magazine
3    const letterCount = new Array(26).fill(0);
4
5    // Iterate over each character in the 'magazine' string
6    for (const char of magazine) {
7        // Increment the count corresponding to the current character
8        letterCount[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
9    }
10
11    // Iterate over each character in the 'ransomNote' string
12    for (const char of ransomNote) {
13        // Get the index of the current character in 'letterCount' array
14        // and decrement the frequency count of the corresponding character
15        const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
16        letterCount[index]--;
17      
18        // If the frequency count goes negative, we do not have enough of this character in the magazine
19        if (letterCount[index] < 0) {
20            return false;
21        }
22    }
23
24    // If we have not returned false by this point, it means we have enough characters for the ransomNote
25    return true;
26}
27

Time and Space Complexity

The time complexity of the function canConstruct is O(m + n), where m is the length of the ransomNote string and n is the length of the magazine string. This is because the function first counts the occurrences of each character in the magazine string, which takes O(n) time, and then iterates through each character in the ransom note, which takes O(m) time. Each character decrement and comparison is an O(1) operation, thus the total time for the loop is O(m). Combined, it leads to O(m + n) time complexity.

The space complexity of the function is O(C), where C is the size of the character set involved in the magazine and ransom note. Given that these are likely to be letters from the English alphabet, the size of the character set C is 26. This fixed size of the character set means the space taken to store the counts is independent of the lengths of the input strings and is hence constant.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.