Hash MapsEasyO(n) time · O(1) space

Ransom Note

Mahabharata — The Spy's Coded Letter — Can the Message Be Assembled from Available Tiles?

यस्य अक्षरं यस्मिन् पत्रे उपलभ्यते। तत् संग्रहेण सन्देशं रचय — न्यूनं चेत् — असम्भवम्॥

*If every letter of the message can be found in the available tiles — it can be formed. If any is lacking — it cannot.*

The Story

Given two strings `ransomNote` and `magazine`, return true if `ransomNote` can be constructed using letters from `magazine` (each letter from magazine can only be used once).

For `ransomNote = "aa"`, `magazine = "aab"`: true ('a' appears twice in magazine, 'a' appears twice in ransomNote) For `ransomNote = "aa"`, `magazine = "ab"`: false (only one 'a' in magazine)

A spy assembled a secret coded message ('ransomNote') by cutting letters from a magazine. Can they construct the full message from the available magazine letters?

**Hash map frequency approach:** 1. Count frequency of each letter in `magazine` 2. For each letter in `ransomNote`: decrement its count - If count drops below 0: NOT enough → return false 3. If all letters processed → return true

```java int[] f = new int[26]; for (char c : magazine.toCharArray()) f[c-'a']++; for (char c : ransomNote.toCharArray()) if (--f[c-'a'] < 0) return false; return true; ```

Trace `ransomNote = "aa"`, `magazine = "aab"`: Magazine: a=2, b=1 Process ransomNote: - 'a': f[a]=2→1 (≥0, ok) - 'a': f[a]=1→0 (≥0, ok) Return true ✓

Trace `ransomNote = "aa"`, `magazine = "ab"`: Magazine: a=1, b=1 - 'a': 1→0 (ok) - 'a': 0→-1 < 0 → return false ✓

"Count from the magazine first — that sets the budget," the spy noted. "Each ransom letter spends from the budget. Overdraft means it's impossible."

The Letter-Hunting Approach

For each character in ransomNote, find and remove it from a copy of magazine. O(n*m) — for each ransom char, scan magazine.

java

public boolean canConstructBruteForce(String ransomNote, String magazine) {
    List<Character> letters = new ArrayList<>();
    for (char c : magazine.toCharArray()) letters.add(c);
    for (char c : ransomNote.toCharArray()) {
        if (!letters.remove((Character) c)) return false;
    }
    return true;
}

The Budget-Decrement Wisdom

Count magazine frequencies (the 'budget'). For each ransomNote char: decrement budget. If any goes negative → return false. O(1) space with int[26].

java

public boolean canConstruct(String ransomNote, String magazine) {
    int[] f = new int[26];
    for (char c : magazine.toCharArray()) f[c - 'a']++;
    for (char c : ransomNote.toCharArray())
        if (--f[c - 'a'] < 0) return false;
    return true;
}

Step-by-Step Walkthrough

ransomNote="b", magazine="aab"
Mag: a=2,b=1
Process 'b': f[b]=1→0. ≥0.
Return true ✅

Deep Insight

**The decrement-and-check pattern:** Count the supplier (magazine), consume from the consumer (ransomNote). This O(n) pattern avoids building frequency maps for both strings — we only need one frequency array.

**Relation to hm-2 (Balloons):** hm-2 builds a frequency map and computes minimum ratio. hm-4 builds one map and decrements. Both exploit the "check if supply meets demand" structure.

**Why not count both and compare?** We could count both and check ransomNote[c] <= magazine[c] for all c. Same O(n) time and O(1) space. The decrement approach is just slightly more concise with early termination.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n*m)	O(m)	Remove from list for each ransom char
Optimal	O(n+m)	O(1)	n = ransomNote length, m = magazine length; int[26]

Pattern Recognition

✅ Can string A be formed from characters in string B?
✅ Count B frequencies; decrement for A chars
✅ Return false if any count < 0
✅ O(1) space with int[26]

**LeetCode Trigger Phrases:**
→ "ransom note" / "can construct from magazine"
→ "is string A a subset of string B's characters?"
→ Frequency budget: supply vs. demand

Bhagavad Gita 2.46

यावान्अर्थ उदपाने सर्वतः सम्प्लुतोदके। तावान्सर्वेषु वेदेषु ब्राह्मणस्य विजानतः॥

To the Brahmin who has realized the Self, all the Vedas are of as little use as a small well when there is a flood of water on all sides.

Connection: The magazine is the treasury of letters — a vast resource. The ransom note is the specific demand. The algorithm checks if the treasury is sufficient for the demand — not seeking more than needed, not wasting what is available. Like the realized sage who uses exactly what dharma requires from the infinite Vedic treasury, the algorithm draws precisely the letters it needs and no more, stopping the moment the supply is exhausted.