LESSON 237 OF 347 · HASH TABLE

Ransom Note in C#: O(n + m) with Character 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 8

Guided

Ctrl + Enter to check

Ransom Note in C#, 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, where each letter in the magazine may be used only once, and false otherwise.

With ransomNote = "aa" and magazine = "abb" the answer is false: the note needs two a's and the magazine has one. With magazine = "aab" the answer is true. The statement asks for O(n + m) time and O(Σ) extra space, where Σ is the size of the alphabet, here the 26 lowercase letters.

Approach: compare letter counts

You do not need to simulate cutting letters out in order. The order of letters in the note does not matter, and neither does the order in the magazine. What matters is how many times each letter occurs. The note can be built exactly when, for every letter, the magazine has at least as many copies as the note needs.

So count the letters of both strings in two dictionaries, ransomFreq and magazineFreq, each mapping a character to its count. Then check each letter from 'a' to 'z': if the note needs more than the magazine has, the answer is false. If no letter fails, the answer is true.

Counting both strings is linear in their lengths, and the final check looks at 26 letters, a constant. The dictionaries hold at most one entry per distinct letter, so the extra space depends on the alphabet and not on the input length.

For the second example, ransomFreq ends as {a: 2} and magazineFreq as {a: 2, b: 1}. At 'a' the note needs 2 and the magazine has 2, which is enough. Every other letter needs 0, so nothing fails and the result is true. A plain array of 26 counters would also work for lowercase letters. This lesson uses dictionaries because they handle any character without index arithmetic.

Step by step

Create the two dictionaries, both of type Dictionary<char, int>: character to count.
Loop over the note's characters. foreach (char c in ransomNote.ToCharArray()) gives each character in turn.
Increment the count. Assign GetValueOrDefault(c, 0) + 1 back to ransomFreq[c]. For a letter seen for the first time, the default 0 makes the count 1. Reading a missing key through the indexer would throw, which is why GetValueOrDefault is used.
Loop over the magazine's characters in the same way. The loop variable c exists only inside its loop, so reusing the name is fine.
Update magazineFreq exactly like the first one.
Check every lowercase letter. A for loop with a char c from 'a' to 'z' inclusive visits the 26 letters.
Fail on a shortage. If the note's count for c is greater than the magazine's, return false. A letter that never appeared reads as 0 from either dictionary.
Return true after the loop: no letter was short.

The solution in C#

class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        Dictionary<char, int> ransomFreq = new Dictionary<char, int>();
        Dictionary<char, int> magazineFreq = new Dictionary<char, int>();
        foreach (char c in ransomNote.ToCharArray()) {
            ransomFreq[c] = ransomFreq.GetValueOrDefault(c, 0) + 1;
        }
        foreach (char c in magazine.ToCharArray()) {
            magazineFreq[c] = magazineFreq.GetValueOrDefault(c, 0) + 1;
        }
        for (char c = 'a'; c <= 'z'; ++c) {
            if (ransomFreq.GetValueOrDefault(c, 0) > magazineFreq.GetValueOrDefault(c, 0)) {
                return false;
            }
        }
        return true;
    }
}

C# details worth noting:

char is a number underneath. A char is a 16-bit UTF-16 code unit, and the letters 'a' to 'z' are consecutive. That is why c <= 'z' and ++c work in a loop header.
Characters use single quotes, strings use double quotes. 'a' is a char, "a" is a string, and a Dictionary<char, int> needs char keys.
Strings are enumerable. You can write foreach (char c in ransomNote) directly. ToCharArray() makes an array copy first, which is not needed, but harmless.
GetValueOrDefault(key, fallback) returns the fallback for a missing key, with no exception and no change to the dictionary.
Strings are immutable. The method only reads them, so neither input changes.

Complexity

Time: O(n + m), with n the length of the note and m the length of the magazine. Each character is counted once at O(1) average cost, and the final loop runs 26 times.

Space: O(Σ). Each dictionary has at most one entry per distinct character, which is at most 26 for lowercase text.

Edge cases and common mistakes

An empty note. CanConstruct("", "") returns true, because nothing is needed. An empty magazine only works with an empty note.
Enough letters but not in the right amount. "aa" with "abb" fails because 2 > 1 for 'a'. The magazine having other letters does not help.
A bigger magazine is fine. Extra letters in the magazine never matter, so "abba" from "aabb" is true.
Only checking presence. Testing whether each letter of the note appears in the magazine ignores how many times. That would wrongly accept "aa" with "abb".
Letters outside 'a' to 'z'. The final loop looks only at lowercase letters. A note such as "A" with an empty magazine would pass, because the uppercase letter is never checked. That is fine for lowercase-only input. For wider input, loop over the keys of ransomFreq instead.
Indexing a missing key. ransomFreq[c] on the right-hand side throws KeyNotFoundException for any letter the note lacks.

Testing

ransomNote = "aa", magazine = "abb" gives false.
ransomNote = "aa", magazine = "aab" gives true.
ransomNote = "abba", magazine = "aabb" gives true.
ransomNote = "", magazine = "" gives true.

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free