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.

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

• Invariant: counts always reflect remaining available letters.
• The map counts/associations are updated consistently per element.
• Lookups use this exact state, so decisions are based on full prior data.
• Therefore the result is correct for the entire input.

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).
• Using a map when a 26-count array is enough.

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.