Start learning free

LESSON 262 OF 415 · HASH TABLE

Ransom Note in Swift: Counting Letters with Dictionaries

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 8
    Ctrl + Enter to check

    SWIFT · HASH TABLE

    Ransom Note in Swift, 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 magazine letter can be used only once, and false otherwise.

    With ransomNote = "aa" and magazine = "abb" the answer is false: the note needs two as and the magazine has one. With magazine = "aab" the answer is true.

    The statement asks for O(n + m) time and extra space proportional to the alphabet size, which is a fixed constant.

    Approach: compare letter counts

    The order of letters in either string doesn't matter. The note "abba" and the note "aabb" need the same letters, and so do the magazines "aaabbb" and "ababab". 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.

    So count the letters of each string into a dictionary, then compare the counts letter by letter. Searching the magazine for each note letter and crossing it off would take O(n * m) time, and the counting approach reads each string once.

    For "abba" and "ababab", the note needs a: 2, b: 2 and the magazine has a: 3, b: 3. Every needed count is covered, so the answer is true.

    Counting both strings is also what makes the repeated-letter case work. A note that needs three as is only satisfied by a magazine with at least three, and the comparison catches that without any bookkeeping about which magazine letters have been used.

    Step by step

    1. Create two dictionaries, ransomFreq and magazineFreq, both of type [Character: Int], mapping each character to how often it occurs. They are var, since they are filled in.
    2. Count the note. Loop for c in ransomNote. A String is a sequence of Character values, so the loop visits one character at a time.
    3. Increment with a default. ransomFreq[c, default: 0] += 1 treats a letter that isn't in the dictionary yet as 0, so no existence check is needed.
    4. Count the magazine the same way into magazineFreq. Reusing the name c is fine, because each loop variable exists only inside its own loop.
    5. Walk the alphabet. A loop over charCode in 97...122, the codes of a to z. The closed range includes both ends.
    6. Convert the code to a character. Character(UnicodeScalar(charCode)!) gives c. UnicodeScalar(_:) is failable because not every integer is a valid scalar, so the result is force-unwrapped. For 97 through 122 it always succeeds.
    7. Compare the counts. A plain dictionary subscript returns an optional, and ?? 0 makes a missing letter count as 0. If the note needs more of the letter than the magazine has, return false.
    8. Return true. Reaching the end means every letter had enough copies.

    The solution in Swift

    class Solution {
    func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {
        var ransomFreq: [Character: Int] = [:]
        var magazineFreq: [Character: Int] = [:]
        for c in ransomNote {
            ransomFreq[c, default: 0] += 1
        }
        for c in magazine {
            magazineFreq[c, default: 0] += 1
        }
        for charCode in 97...122 {
            let c = Character(UnicodeScalar(charCode)!)
            if (ransomFreq[c] ?? 0) > (magazineFreq[c] ?? 0) {
                return false
            }
        }
        return true
    }
}

    Swift details worth knowing:

    • Characters. The dictionary keys are Character values, not String values. In Swift, a String can't be indexed by integers, but iterating it with for c in works naturally.
    • The default: subscript can both read and write. dict[c, default: 0] += 1 reads the value (or 0), adds one and stores the result.
    • Optional comparison. ransomFreq[c] is an Int?. Comparing optionals with > isn't allowed, which is why both sides are unwrapped with ?? 0.
    • The parentheses around each ?? 0 expression aren't strictly required, because ?? binds tighter than comparison operators, but they make the intent clear at a glance.
    • Range of integers. 97...122 is a ClosedRange<Int>. Writing 97..<122 would stop before z.
    • The alphabet only. The check covers lowercase a to z. Characters outside that range, such as capitals, digits or spaces, are counted but never compared, so this version suits inputs made of lowercase letters. To handle any character, loop over the keys of ransomFreq instead.

    Complexity

    Time: O(n + m), where n is the length of the note and m the length of the magazine. Each string is read once, and the final loop always runs 26 times.

    Space: O(Σ), where Σ is the alphabet size. Each dictionary holds at most one entry per distinct letter, which is at most 26 for lowercase text.

    Edge cases and common mistakes

    • Empty note. It needs nothing, so canConstruct("", "abc") is true.
    • Empty magazine. canConstruct("abc", "") is false.
    • Letters used twice. Checking only that each note letter appears in the magazine would say true for "aa" and "abb". The counts are what matter.
    • Comparing in the wrong direction. The note's count must not exceed the magazine's. A magazine may have extra letters.
    • Forgetting ?? 0. A letter missing from a dictionary is nil, and comparing it as a number doesn't compile.
    • Crashing on a missing key. Force-unwrapping with ! where a key may be absent stops the program.
    • Letters outside a to z. This version doesn't compare them.

    Testing

    • "aa" and "abb" give false.
    • "aa" and "aab" give true.
    • "abba" and "ababab" give true.
    • "" and "abc" give true, and "abc" and "" give false.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free