LeetCode 383: Ransom Note

Problem Restatement

We are given two strings:

ransomNote
magazine

We need to decide whether ransomNote can be built using letters from magazine.

Each letter from magazine can be used at most once.

So we need enough copies of every character required by ransomNote.

For example, if ransomNote = "aa" and magazine = "ab", the answer is False, because magazine has only one a.

Input and Output

Example function shape:

def canConstruct(ransomNote: str, magazine: str) -> bool:
    ...

Examples

Example 1:

ransomNote = "a"
magazine = "b"

The note needs one a.

The magazine has no a.

So the answer is:

False

Example 2:

ransomNote = "aa"
magazine = "ab"

The note needs two a letters.

The magazine has only one a.

So the answer is:

False

Example 3:

ransomNote = "aa"
magazine = "aab"

The note needs two a letters.

The magazine has two a letters.

So the answer is:

True

First Thought: Search and Remove

A direct idea is to process each character in ransomNote.

For each character, search for it inside magazine.

If found, remove one copy from magazine.

If not found, return False.

For example:

ransomNote = "aa"
magazine = "aab"

Use the first a, leaving:

"ab"

Use the second a, leaving:

"b"

Now the note can be constructed.

This works logically, but strings are immutable in Python. Removing a character creates a new string, which costs time. Repeated searching and removing can become too slow for input length up to 10^5.

Key Insight

We only care about character counts.

The order of letters in magazine does not matter.

We need to know whether magazine contains at least as many copies of each character as ransomNote.

So we count the letters in magazine, then consume them while scanning ransomNote.

Algorithm

Create an array of size 26.

Each index represents one lowercase English letter.

count[0] -> number of 'a'
count[1] -> number of 'b'
count[2] -> number of 'c'

First, scan magazine and count every letter.

Then scan ransomNote.

For each character:

1. Convert it to an index from 0 to 25.
2. Decrease its count.
3. If the count becomes negative, return False.

If the whole ransomNote is processed successfully, return True.

Correctness

The array count stores how many unused copies of each magazine letter remain.

After scanning magazine, count correctly records the available supply of every letter.

When processing ransomNote, each character uses one available copy of that same character. Decrementing the corresponding count models this use.

If a count becomes negative, then the note requires more copies of that character than the magazine provides. In that case, construction is impossible, so returning False is correct.

If no count becomes negative, every required letter was matched with a distinct magazine letter. Since each decrement consumes one copy, no magazine letter is reused.

Therefore returning True is correct.

Complexity

Let n = len(ransomNote) and m = len(magazine).

Implementation

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        count = [0] * 26

        for ch in magazine:
            idx = ord(ch) - ord("a")
            count[idx] += 1

        for ch in ransomNote:
            idx = ord(ch) - ord("a")
            count[idx] -= 1

            if count[idx] < 0:
                return False

        return True

Code Explanation

We create a fixed-size frequency table:

count = [0] * 26

Then we count letters from magazine:

for ch in magazine:
    idx = ord(ch) - ord("a")
    count[idx] += 1

The expression:

ord(ch) - ord("a")

maps:

'a' -> 0
'b' -> 1
'c' -> 2
...
'z' -> 25

Then we consume letters required by ransomNote:

for ch in ransomNote:
    idx = ord(ch) - ord("a")
    count[idx] -= 1

If the count becomes negative:

if count[idx] < 0:
    return False

then the magazine does not contain enough of that character.

If the loop finishes, all letters were available:

return True

Testing

def test_solution():
    s = Solution()

    assert s.canConstruct("a", "b") is False
    assert s.canConstruct("aa", "ab") is False
    assert s.canConstruct("aa", "aab") is True
    assert s.canConstruct("abc", "cba") is True
    assert s.canConstruct("aabbcc", "abcabc") is True
    assert s.canConstruct("aabbcc", "abcab") is False
    assert s.canConstruct("zz", "z") is False

    print("all tests passed")

test_solution()

Test meaning: