Jobs

Interviews

Discussions

Ransom Note

Easy

Disney

0 views

Topics:

ArraysStrings

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

Ransom Note

Easy

Disney

0 views

Topics:

ArraysStrings

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the input strings `ransomNote` and `magazine` case-sensitive? Should I treat uppercase and lowercase letters as distinct?
Can the input strings `ransomNote` and `magazine` be empty or null? If so, what should I return?
Are there any limitations on the character set used in the strings `ransomNote` and `magazine`? (e.g., only ASCII characters, or Unicode characters)
If the `magazine` string contains enough characters to construct the `ransomNote` multiple times, should I still return true?
Is there a maximum length for the input strings `ransomNote` and `magazine`? This will help me understand memory constraints.

Brute Force Solution

Approach

The problem asks if we can construct a ransom note using letters from a magazine. The brute force approach directly tries to 'use' each letter in the magazine to build the ransom note, one letter at a time, checking if we have enough.

Here's how the algorithm would work step-by-step:

For each letter in the ransom note, we will try to find it in the magazine.
If we find the letter in the magazine, we will 'use' it by virtually removing it from the magazine.
We then proceed to the next letter in the ransom note and repeat the process of searching in the magazine.
If at any point, we can't find a letter from the ransom note in the remaining magazine letters, it means we cannot construct the ransom note.
If we successfully find all the letters from the ransom note in the magazine, then we know we can construct the ransom note.

Code Implementation

def can_construct_ransom_note(ransom_note, magazine): 
    magazine_letters = list(magazine)

    for ransom_note_letter in ransom_note:
        # Iterate through each letter in ransom note

        found_match = False
        for magazine_letter_index in range(len(magazine_letters)):
            if magazine_letters[magazine_letter_index] == ransom_note_letter:
                # If we find the letter, mark it and break

                magazine_letters.pop(magazine_letter_index)
                found_match = True
                break

        if not found_match:
            # If letter not found, note can't be constructed

            return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each character of the ransomNote (length m). For each character in the ransomNote, it searches for a matching character within the magazine (length n). In the worst-case scenario, for every character in the ransomNote, the entire magazine needs to be scanned. Therefore, the time complexity is proportional to the product of the lengths of the ransomNote and the magazine, resulting in O(m*n).

Space Complexity

O(1) – The provided algorithm modifies the 'magazine' virtually by searching and 'removing' characters. However, based on the plain English explanation, it doesn't explicitly use any auxiliary data structures like lists, dictionaries, or sets to store intermediate results or track used characters. The operations are performed in place, conceptually altering the magazine as it iterates through the ransom note. Therefore, the auxiliary space complexity is constant, independent of the lengths of the ransom note or the magazine.

Optimal Solution

Approach

The most efficient way to solve this problem is to count how many times each letter appears in the magazine. Then, we check if we have enough of each letter to create the ransom note. If we do, we can make the note; otherwise, we cannot.

Here's how the algorithm would work step-by-step:

First, count how many times each letter appears in the magazine. Think of this as creating an inventory of letters available.
Next, go through the ransom note and, for each letter, check if it's available in our magazine inventory.
If we find a letter in the ransom note that's not in the magazine inventory (or we don't have enough of it), we immediately know we can't create the note.
If we successfully make it through the entire ransom note, meaning we found enough of each letter, we know we can create the note.

Code Implementation

def canConstruct(ransomNote, magazine):
    magazine_letter_counts = {}

    for letter in magazine:
        magazine_letter_counts[letter] = magazine_letter_counts.get(letter, 0) + 1

    # We will iterate over the ransom note.
    for letter in ransomNote:
        if letter not in magazine_letter_counts or magazine_letter_counts[letter] == 0:
            return False

        # Decrement the count after processing a letter
        magazine_letter_counts[letter] -= 1

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m + n) – The provided solution involves iterating through the magazine string once to count the frequency of each character, which takes O(m) time, where m is the length of the magazine. Then, the solution iterates through the ransom note string to check if each character is available in the magazine's character count, taking O(n) time, where n is the length of the ransom note. Since these operations are performed sequentially, the overall time complexity is O(m + n).

Space Complexity

O(1) – The solution's space complexity hinges on the 'magazine inventory'. The most efficient implementation typically uses a hash map or an array to store the counts of each character present in the magazine. Since the number of possible characters is limited (e.g., 26 for lowercase English letters), the inventory will have a maximum fixed size irrespective of the magazine's or ransom note's length. This fixed-size inventory dictates a constant amount of extra space used, independent of the input size N (where N could represent the combined lengths of the ransom note and magazine).

Edge Cases

Case	How to Handle
ransomNote is an empty string	Return true because an empty ransomNote can always be constructed from any magazine.
magazine is an empty string and ransomNote is not	Return false because ransomNote cannot be constructed from an empty magazine.
Both ransomNote and magazine are empty strings	Return true because an empty ransomNote can always be constructed from an empty magazine.
ransomNote is longer than magazine	Return false because ransomNote cannot be constructed if it's longer than magazine.
ransomNote contains characters not present in magazine	Return false because the ransomNote cannot be constructed with missing characters.
ransomNote requires more occurrences of a character than magazine provides	The frequency count check will ensure that the solution returns false if sufficient instances do not exist.
Large input strings that could cause performance issues	Using a hash map/frequency counter approach ensures O(m+n) time complexity, which scales linearly with input size.
Input strings contain non-ASCII characters (Unicode)	Hash map handles Unicode characters correctly as keys, maintaining correct character counts.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the input strings `ransomNote` and `magazine` case-sensitive? Should I treat uppercase and lowercase letters as distinct?
Can the input strings `ransomNote` and `magazine` be empty or null? If so, what should I return?
Are there any limitations on the character set used in the strings `ransomNote` and `magazine`? (e.g., only ASCII characters, or Unicode characters)
If the `magazine` string contains enough characters to construct the `ransomNote` multiple times, should I still return true?
Is there a maximum length for the input strings `ransomNote` and `magazine`? This will help me understand memory constraints.

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

For each letter in the ransom note, we will try to find it in the magazine.
If we find the letter in the magazine, we will 'use' it by virtually removing it from the magazine.
We then proceed to the next letter in the ransom note and repeat the process of searching in the magazine.
If at any point, we can't find a letter from the ransom note in the remaining magazine letters, it means we cannot construct the ransom note.
If we successfully find all the letters from the ransom note in the magazine, then we know we can construct the ransom note.

Code Implementation

def can_construct_ransom_note(ransom_note, magazine): 
    magazine_letters = list(magazine)

    for ransom_note_letter in ransom_note:
        # Iterate through each letter in ransom note

        found_match = False
        for magazine_letter_index in range(len(magazine_letters)):
            if magazine_letters[magazine_letter_index] == ransom_note_letter:
                # If we find the letter, mark it and break

                magazine_letters.pop(magazine_letter_index)
                found_match = True
                break

        if not found_match:
            # If letter not found, note can't be constructed

            return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each letter appears in the magazine. Think of this as creating an inventory of letters available.
Next, go through the ransom note and, for each letter, check if it's available in our magazine inventory.
If we find a letter in the ransom note that's not in the magazine inventory (or we don't have enough of it), we immediately know we can't create the note.
If we successfully make it through the entire ransom note, meaning we found enough of each letter, we know we can create the note.

Code Implementation

def canConstruct(ransomNote, magazine):
    magazine_letter_counts = {}

    for letter in magazine:
        magazine_letter_counts[letter] = magazine_letter_counts.get(letter, 0) + 1

    # We will iterate over the ransom note.
    for letter in ransomNote:
        if letter not in magazine_letter_counts or magazine_letter_counts[letter] == 0:
            return False

        # Decrement the count after processing a letter
        magazine_letter_counts[letter] -= 1

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
ransomNote is an empty string	Return true because an empty ransomNote can always be constructed from any magazine.
magazine is an empty string and ransomNote is not	Return false because ransomNote cannot be constructed from an empty magazine.
Both ransomNote and magazine are empty strings	Return true because an empty ransomNote can always be constructed from an empty magazine.
ransomNote is longer than magazine	Return false because ransomNote cannot be constructed if it's longer than magazine.
ransomNote contains characters not present in magazine	Return false because the ransomNote cannot be constructed with missing characters.
ransomNote requires more occurrences of a character than magazine provides	The frequency count check will ensure that the solution returns false if sufficient instances do not exist.
Large input strings that could cause performance issues	Using a hash map/frequency counter approach ensures O(m+n) time complexity, which scales linearly with input size.
Input strings contain non-ASCII characters (Unicode)	Hash map handles Unicode characters correctly as keys, maintaining correct character counts.