Start learning free

LESSON 238 OF 348 · HASH TABLE

Ransom Note in TypeScript: O(n + m) with Letter Counts

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 occurences of each letter in magazine and in ransomNote. How can we achieve this?

We have a data structure specially designed to do that! It is the Hash Map. We should construct two different Hash Maps:
  • ransomFreq, where ransomFreq[c] is the number of occurences of letter c in ransomNote
  • magazineFreq, where magazineFreq[c] is the number of occurences of letter c in magazine
How should we populate these Hash Maps?

Using a for loop, we will iterate with a variable c through every character of ransomNote and increment ransomFreq[c]. We will do the same for magazineFreq. What should we do after we have populated these hash maps?

Using a for loop, we should iterate through each character c of the alphabet (from 'a' to 'z') and check if ransomFreq[c] > magazineFreq[c]. 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

    TYPESCRIPT · HASH TABLE

    Ransom Note in TypeScript, explained

    Problem overview

    The method canConstruct receives two strings, ransomNote and magazine. It returns true if the note can be built from letters of the magazine, and false otherwise. Each letter of the magazine can be used only once, but the letters can be taken in any order.

    With ransomNote = "aa" and magazine = "abb", the note needs two a's and the magazine has only one, so the answer is false. With magazine = "aab" there are two a's, so the answer is true. The unused b doesn't matter.

    The statement asks for O(n + m) time, where n and m are the lengths of the two strings, and extra space proportional to the alphabet size, not to the string lengths.

    Approach: compare letter counts

    Since order doesn't matter, the question is only about quantities. The note can be built exactly when, for every letter, the magazine has at least as many copies as the note needs. The note "abba", for example, needs two a's and two b's, and both "aaabbb" and "ababab" satisfy that.

    So count how often each letter occurs in the note, count the same for the magazine, then check each letter of the alphabet: if the note needs more than the magazine has, return false. If every letter passes, return true.

    Searching the magazine for each letter of the note would take O(n * m) time. Counting reads each string once, which gives O(n + m). The alphabet loop runs 26 times whatever the input, so it adds only a constant.

    Step by step

    1. Create two count tables. ransomFreq and magazineFreq are empty objects typed {[key: string]: number}. That type says any string key maps to a number, so a character can be used as the key.
    2. Count the note. Loop over ransomNote with for...of, which visits one character at a time as c.
    3. Increment. Set ransomFreq[c] to (ransomFreq[c] || 0) + 1. The first time a character appears its entry is missing, which reads as undefined. || 0 turns that into 0.
    4. Count the magazine with the same kind of loop. The variable c exists only inside its own loop, so reusing the name is fine.
    5. Update magazineFreq[c] in the same way.
    6. Loop over the alphabet. Use a numeric charCode that goes from 'a'.charCodeAt(0) to 'z'.charCodeAt(0), inclusive.
    7. Turn the code into a letter. String.fromCharCode(charCode) gives the one-character string c to use as a key.
    8. Compare. If (ransomFreq[c] || 0) is greater than (magazineFreq[c] || 0), the magazine can't supply that letter, so return false.
    9. Return true after the loop. It is reached only if no letter failed.

    The solution in TypeScript

    class Solution {
    canConstruct(ransomNote: string, magazine: string): boolean {
        let ransomFreq: {[key: string]: number} = {};
        let magazineFreq: {[key: string]: number} = {};
        for (let c of ransomNote) {
            ransomFreq[c] = (ransomFreq[c] || 0) + 1;
        }
        for (let c of magazine) {
            magazineFreq[c] = (magazineFreq[c] || 0) + 1;
        }
        for (let charCode = 'a'.charCodeAt(0); charCode <= 'z'.charCodeAt(0); charCode++) {
            let c = String.fromCharCode(charCode);
            if ((ransomFreq[c] || 0) > (magazineFreq[c] || 0)) {
                return false;
            }
        }
        return true;
    }
}

    The TypeScript details worth a closer look:

    • Index signatures. The type {[key: string]: number} describes an object used as a dictionary. It is only a compile-time description. At run time the object is empty until you add keys.
    • Missing keys read as undefined. The type says number, but an absent key gives undefined at run time. Types are erased when TypeScript compiles to JavaScript, so nothing in the compiled code fills in a default. The || 0 does that job.
    • Why the final comparison needs || 0 too. Any comparison with undefined is false. Without the defaults, a letter that is in the note but missing from the magazine would give 1 > undefined, which is false, and the method would wrongly return true.
    • for...of on a string iterates over characters, not over indices. Use it when you only need the characters.
    • Character codes. charCodeAt(0) returns the numeric code of the first character: 97 for 'a' and 122 for 'z'. The letters in between have consecutive codes, which is what makes the alphabet loop work.
    • The loop covers only a to z. The check looks at lowercase English letters only. The method is correct for inputs made of those letters. Characters outside that range are counted but never compared.

    Complexity

    Time: O(n + m). Each string is read once, with constant work per character, and the alphabet loop runs exactly 26 times.

    Space: O(Σ), where Σ is the alphabet size. Each table holds at most one entry per distinct character, which is at most 26 for lowercase letters. The space does not grow with the length of the strings.

    Edge cases and common mistakes

    • An empty note. canConstruct("", "abc") is true: nothing needs to be built, and no letter exceeds its count.
    • An empty magazine. canConstruct("a", "") is false, because the note needs a letter the magazine doesn't have.
    • Reordered letters. "abba" from "aabb" is true. Only the counts matter.
    • A magazine with extra letters. Extra letters are fine. Only the letters the note needs are compared.
    • Checking only whether a letter appears. The note "aa" needs two a's, so "the magazine contains an a" is not enough.
    • Forgetting || 0. Without it, the first increment computes undefined + 1, which is NaN, and every later check fails or passes for the wrong reason.
    • Using < instead of >. The method must reject a letter when the note needs more copies than the magazine has.

    Testing

    • ransomNote = "aa", magazine = "abb" gives false.
    • ransomNote = "aa", magazine = "aab" gives true.
    • ransomNote = "abba", magazine = "aabb" gives true.
    • ransomNote = "", magazine = "abc" gives true.
    • ransomNote = "a", magazine = "" gives false.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free