Ransom Note Frequency Counting DSA Solution

Learning Outcome

After this lesson, you should be able to use a frequency table as an availability inventory and consume characters safely.

Problem Statement

Given ransomNote and magazine, return true if ransomNote can be constructed using each magazine character at most once.

Input	Output	Why
`ransomNote = "aa", magazine = "aab"`	`true`	The magazine has two a characters, enough to build aa.

Brute Force Approach

For each ransom character, scan the magazine for an unused matching character. This is slow and awkward to track.

Optimized Approach

Count magazine characters once. For each ransom character, decrement its available count and fail immediately if it goes below zero.

Exact Pseudocode

freq = counts of magazine
for ch in ransomNote:
  freq[ch] -= 1
  if freq[ch] < 0:
    return false
return true

Reference Code

class Solution:
    def canConstruct(self, ransomNote, magazine):
        freq = {}
        for ch in magazine:
            freq[ch] = freq.get(ch, 0) + 1

        for ch in ransomNote:
            freq[ch] = freq.get(ch, 0) - 1
            if freq[ch] < 0:
                return False

        return True

Sample Dry Run

Step	State	Result
Count magazine	a:2, b:1	Availability ready
Need first a	a count becomes 1	Still possible
Need second a	a count becomes 0	Still possible
Finish	No shortage found	return true

Complexity

Measure	Value	Reason
Time	O(n + m)	Both strings are scanned once.
Space	O(1)	For lowercase English letters, the frequency array has fixed size.

Edge Cases

An empty ransom note returns true.
Repeated needed characters require repeated availability.
Set membership alone is not enough.

Interview Checklist

Count magazine, not ransomNote, as the available inventory.
Fail as soon as a count goes below zero.
Use the right character range for the prompt.

FAQs

Why not use a set?

A set only says whether a character exists, not how many copies are available.

Why decrement while scanning ransomNote?

It simulates consuming each required character once.

What is the core pattern?

Frequency availability counting.

Ransom Note: Character Availability Pattern