Ransom Note (LC 383)

Pattern: Hashing / Frequency Maps
Difficulty: Easy
Key Concept: You can build the note only if every character’s demand in ransomNote is covered by the supply in magazine, with each magazine letter used at most once.

Problem Statement

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using letters from magazine.

Each character in magazine may be used at most once in ransomNote.

Input

• ransomNote — string
• magazine — string

Output

• true if the note can be built from the magazine’s letters (without reusing a magazine letter beyond its count), else false

---

1. Algorithm & Pseudocode

Brute force (search and consume)

FOR each character c needed in ransomNote:
    FIND index of c in magazine (e.g. indexOf)
    IF not found:
        RETURN false
    REMOVE that character from magazine (e.g. deleteCharAt)
RETURN true

Optimal (frequency counts)

BUILD count[26] from magazine: increment for each char
FOR each character c in ransomNote:
    index = c - 'a'
    count[index]--
    IF count[index] < 0:
        RETURN false
RETURN true

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why brute force is slow:
Each indexOf can scan most of magazine, and each removal shifts characters. Roughly (O(n \cdot m)) for note length (n) and magazine length (m).

Why counting works:
Think of the magazine as inventory. First, record how many of each letter you have. For each letter the note needs, decrement. If any count goes negative, you needed more of that letter than you had.

Why we only check < 0?
We never need to verify “exact match” at the end: if we never go negative, we never asked for more than available for any letter.

Empty note:
If ransomNote is empty, we need no letters—typically return true (check problem statement; LeetCode treats empty note as constructible).

---

3. The Dry Run

Sample: ransomNote = "aa", magazine = "aab"

Step 1 — count magazine "aab":

Step	Char	Index	Action	count[a]	count[b]	(others 0)
1	a	0	count[0]++	1	0	…
2	a	0	count[0]++	2	0	…
3	b	1	count[1]++	2	1	…

After magazine: a=2, b=1.

Step 2 — process ransomNote = "aa":

Step	Char	Index	Action	count[a]	count[b]	Check
1	a	0	count[0]–	1	1	1 ≥ 0 ✓
2	a	0	count[0]–	0	1	0 ≥ 0 ✓

No negative counts → return true.

Contrast: If ransomNote = "aaa" after the same magazine, after third a we would get count[a] = -1 → false.

---

4. Java Solution

Brute Force

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        StringBuilder mag = new StringBuilder(magazine);
        for (int i = 0; i < ransomNote.length(); i++) {
            char c = ransomNote.charAt(i);
            int idx = mag.indexOf(c);
            if (idx < 0) {
                return false;
            }
            mag.deleteCharAt(idx);
        }
        return true;
    }
}

Time: (O(n \cdot m)) in the worst case (each search + delete can be linear in current magazine length).
Space: (O(m)) for the StringBuilder copy of magazine.

Optimal

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] count = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            count[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            int idx = ransomNote.charAt(i) - 'a';
            count[idx]--;
            if (count[idx] < 0) {
                return false;
            }
        }
        return true;
    }
}

Time: (O(n + m)) where (n = |ransomNote|), (m = |magazine|).
Space: (O(1)) extra (26 counters).

---

5. The “Java vs. Others” Edge

• int[26]: Same pattern as other “lowercase only” problems; map with char - 'a'.
• String.indexOf + StringBuilder.deleteCharAt: Illustrates brute force in Java but is slow due to repeated linear scans and shifting—good to mention in interviews, then replace with counts.
• C++: Identical frequency array with vector<int> count(26) or a plain array.
• Unicode: Use HashMap<Character, Integer> if characters are not limited to a–z.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n \cdot m))	(O(m))	Repeated search/remove on mutable copy of magazine.
Optimal	(O(n + m))	(O(1))	Single pass per string + fixed alphabet array.