LeetCode 383 - Ransom Note

This problem asks whether it is possible to construct the string ransomNote using characters taken from the string magazine. Each character in magazine can only be used once, which means character frequency matters.

leetcodeeasyhash-tablestringcounting

LeetCode Problem 383

Difficulty: 🟢 Easy
Topics: Hash Table, String, Counting

Solution

Problem Understanding

This problem asks whether it is possible to construct the string ransomNote using characters taken from the string magazine. Each character in magazine can only be used once, which means character frequency matters. If ransomNote requires more occurrences of a letter than magazine contains, the answer must be false.

In other words, we need to verify that every letter needed by ransomNote exists in magazine in sufficient quantity.

The input consists of two lowercase English strings:

  • ransomNote, the string we want to construct
  • magazine, the source of available letters

The expected output is a boolean:

  • true if all required letters can be supplied
  • false otherwise

The constraints are important:

  • Both strings can be as large as 10^5
  • Only lowercase English letters are used

The large input size tells us that inefficient repeated searching will likely be too slow. Since the alphabet is limited to only 26 lowercase letters, counting frequencies becomes a very natural and efficient strategy.

Several edge cases are important to consider:

  • ransomNote may require a letter that does not exist in magazine
  • ransomNote may require multiple copies of a letter while magazine contains fewer copies
  • magazine may contain many extra unused letters
  • The strings may be very large, so repeated scans of magazine should be avoided

Because the problem guarantees lowercase English letters only, we can use either a hash map or a fixed-size array of length 26.

Approaches

Brute Force Approach

A straightforward approach is to process each character in ransomNote one by one and search for a matching unused character inside magazine.

One possible implementation is:

  1. Convert magazine into a mutable list
  2. For each character in ransomNote
  • Search through magazine
  • If the character is found, remove or mark it as used
  • If not found, return false
  1. If all characters are matched, return true

This approach is correct because it explicitly simulates taking letters from the magazine one at a time.

However, it is inefficient. For every character in ransomNote, we may scan most of magazine. If both strings are length n, the total work can become O(n^2).

With input sizes up to 10^5, quadratic time is far too slow.

Optimal Approach

The key observation is that the order of characters does not matter, only the number of occurrences of each character matters.

Instead of repeatedly searching for letters, we can count how many times each letter appears in magazine, then subtract counts while processing ransomNote.

For example:

  • magazine = "aab" produces counts:

  • a -> 2

  • b -> 1

Then while reading ransomNote = "aa":

  • Use one a, remaining count becomes 1
  • Use another a, remaining count becomes 0

Since no count ever becomes negative, construction is possible.

This transforms repeated searches into constant-time frequency updates.

Because there are only 26 lowercase letters, this solution is extremely efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × m) O(m) Repeatedly searches and removes characters from magazine
Optimal O(n + m) O(1) Counts character frequencies using a fixed-size array

Algorithm Walkthrough

  1. Create a frequency array of size 26.

Since the input only contains lowercase English letters, we can map:

  • 'a' to index 0
  • 'b' to index 1
  • ...
  • 'z' to index 25

This gives constant-time access to character counts. 2. Traverse the magazine string and count each character.

For every character:

  • Compute its index using ord(char) - ord('a')
  • Increment the corresponding count

After this step, the array stores how many copies of each letter are available. 3. Traverse the ransomNote string.

For every character:

  • Compute its index
  • Decrement the corresponding count

This represents using one copy of that character from the magazine. 4. Check whether any count becomes negative.

If a count becomes negative, it means ransomNote requires more copies of a letter than magazine provides.

In that case, immediately return false. 5. If the loop finishes successfully, return true.

This means every required character was available in sufficient quantity.

Why it works

The algorithm maintains the invariant that the frequency array always represents the remaining unused letters from magazine.

Every decrement corresponds to consuming one character for the ransom note. If any count becomes negative, we have consumed more copies of a character than were originally available, which makes construction impossible.

If all characters are processed without violating this condition, then every required letter existed in sufficient quantity, so the ransom note can be constructed.

Python Solution

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

        for char in magazine:
            index = ord(char) - ord('a')
            char_counts[index] += 1

        for char in ransomNote:
            index = ord(char) - ord('a')
            char_counts[index] -= 1

            if char_counts[index] < 0:
                return False

        return True

The implementation begins by creating a fixed-size array called char_counts. Each position represents one lowercase English letter.

The first loop processes magazine and records how many times each character appears. This prepares the available inventory of letters.

The second loop processes ransomNote. Each character decreases the corresponding count because one copy is being consumed.

The moment a count becomes negative, the function returns False. This indicates the ransom note requires more copies of a character than the magazine contains.

If the entire ransom note is processed successfully, the function returns True.

This implementation is efficient because every character is processed exactly once.

Go Solution

func canConstruct(ransomNote string, magazine string) bool {
    charCounts := make([]int, 26)

    for _, char := range magazine {
        index := char - 'a'
        charCounts[index]++
    }

    for _, char := range ransomNote {
        index := char - 'a'
        charCounts[index]--

        if charCounts[index] < 0 {
            return false
        }
    }

    return true
}

The Go implementation follows the same logic as the Python version.

A slice of length 26 stores character frequencies. Go characters are represented as runes during iteration with range, so subtracting 'a' correctly maps each lowercase letter to an index.

No special handling for empty or nil values is required because the problem constraints guarantee valid non-empty lowercase strings.

Integer overflow is not a concern because counts never exceed 10^5, which easily fits inside Go's integer type.

Worked Examples

Example 1

ransomNote = "a"
magazine = "b"

First, count characters from magazine.

Character Count Array Change
b count['b'] = 1

Current counts:

Letter Count
a 0
b 1

Now process ransomNote.

Character Action Result
a decrement count['a'] becomes -1

Since the count became negative, return false.

Example 2

ransomNote = "aa"
magazine = "ab"

Build counts from magazine.

Character Count
a 1
b 1

Process ransomNote.

Step Character Updated Count Result
1 a 0 valid
2 a -1 invalid

The second a is unavailable, so return false.

Example 3

ransomNote = "aa"
magazine = "aab"

Build counts from magazine.

Character Count
a 2
b 1

Process ransomNote.

Step Character Updated Count Result
1 a 1 valid
2 a 0 valid

No count becomes negative, so return true.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) One pass through both strings
Space O(1) Fixed array of size 26

The algorithm processes each character from magazine and ransomNote exactly once. If n is the length of ransomNote and m is the length of magazine, the total runtime is linear.

The space complexity is constant because the frequency array always contains exactly 26 integers regardless of input size.

Test Cases

solution = Solution()

assert solution.canConstruct("a", "b") is False  # missing required character
assert solution.canConstruct("aa", "ab") is False  # insufficient frequency
assert solution.canConstruct("aa", "aab") is True  # enough copies available

assert solution.canConstruct("abc", "cbad") is True  # characters in different order
assert solution.canConstruct("aabbcc", "abcabc") is True  # exact matching frequencies
assert solution.canConstruct("aabbcc", "aabbc") is False  # one character missing

assert solution.canConstruct("z", "z") is True  # smallest valid input
assert solution.canConstruct("zz", "z") is False  # repeated character shortage

assert solution.canConstruct("abc", "def") is False  # no overlapping letters
assert solution.canConstruct("leetcode", "tleeodced") is True  # shuffled valid input

assert solution.canConstruct("aaaaa", "aaaaaaaaaa") is True  # many extra characters
assert solution.canConstruct("abc", "abccccc") is True  # extra unused characters
Test Why
"a", "b" Validates missing character detection
"aa", "ab" Validates insufficient frequency handling
"aa", "aab" Confirms successful construction
"abc", "cbad" Verifies order does not matter
"aabbcc", "abcabc" Checks exact frequency matching
"aabbcc", "aabbc" Detects shortage of one letter
"z", "z" Smallest successful case
"zz", "z" Repeated character shortage
"abc", "def" No common letters
"leetcode", "tleeodced" Larger shuffled valid input
"aaaaa", "aaaaaaaaaa" Many extra available letters
"abc", "abccccc" Extra unused characters do not matter

Edge Cases

One important edge case occurs when ransomNote requires a character that does not exist in magazine at all. For example, "a" and "b". A buggy implementation might continue searching unnecessarily or fail to detect the absence correctly. In this solution, the frequency count for 'a' starts at zero and immediately becomes negative during processing, which correctly returns false.

Another important case is when a character exists in magazine but not enough times. For example, "aa" and "ab". Some naive implementations only check whether a character exists, not whether the frequency is sufficient. This solution handles the issue naturally because each use decrements the count. The second decrement makes the count negative, signaling failure.

A third edge case involves extra unused characters in magazine. For example, "abc" and "abccccc". The algorithm should ignore unnecessary letters and focus only on whether required letters are available. Since unused counts simply remain positive, the implementation correctly returns true.

A final edge case involves very large inputs near the constraint limit. A quadratic solution that repeatedly scans the magazine could time out. This implementation avoids repeated searches entirely and processes both strings in linear time, making it efficient even for strings of length 10^5.