Ransom Note

Given two lowercase strings ransomNote and magazine, return true if you can construct ransomNote using letters from magazine. Each letter in magazine can be used at most once.

Why this is worth learning

Availability is a multiset budget. Seeing a letter once is not enough when the note demands several copies.

Before coding: one-minute experiment

Can note "aa" be constructed from magazine "ab"?

Function signature

func CanConstruct(ransomNote string, magazine string) bool

Inputs / outputs

• ransomNote: target string.
• magazine: available characters.
• Return: true if constructible, else false.

Example

ransomNote = "aa", magazine = "aab"
Output: true

Constraints

• 0 <= len(ransomNote), len(magazine) <= 100_000
• Strings contain only lowercase letters.

Core idea (near-solution)

Count available letters in magazine, then consume them while scanning ransomNote.

Invariant: counts always reflect remaining available letters.

Algorithm (step-by-step)

1. Count each letter in magazine.
2. For each letter in ransomNote:
   • If its count is zero, return false.
   • Otherwise decrement the count.
3. Return true.

Correctness sketch

After counting the magazine, each coordinate is the number of unused copies of one lowercase letter. For each next note byte, a zero budget proves that no unused magazine occurrence can supply it, so failure is necessary. Otherwise decrementing consumes one available copy and preserves the remaining-budget interpretation. The note order imposes no restriction on which magazine occurrence is used, so satisfying every byte is sufficient. After the entire note is processed, an explicit allocation of distinct magazine occurrences exists for all requested letters. Unused magazine copies do not affect validity.

Trace (hand walkthrough)

Example input:
ransomNote = "aa", magazine = "aab"
Output: true

Walk:
- counts from magazine: a=2, b=1
- take first a -> a=1
- take second a -> a=0 -> success

Pitfalls to avoid

• Assuming order matters (it does not).
• Checking only whether a letter exists, without consuming one available copy for each request.

Debugging lens

Test an empty note, abundant irrelevant letters, and exactly one missing repeated letter. This is containment of counts, not equality of the two multisets.

Complexity

• Time: O(n + m)
• Extra space: O(1) (26 counts).

Implementation notes (Go)

• Use a [26]int count array for magazine letters.
• Decrement for ransom letters and fail fast on negative counts.

Reconstruction checkpoint

Can note "aa" be constructed from magazine "ab"?

Return to Hash Map · Module quiz