Ransom Note Algorithm

Can you build the ransom note using only letters from the magazine? Each letter in the magazine can only be used once.

Input: ransomNote = "a", magazine = "b"
Output: false

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

The intuition

Count the available letters in the magazine. Then check if the ransom note's letters fit within those counts. If any letter in the note exceeds what's available, return false.

The quick approach

var canConstruct = function(ransomNote, magazine) {
    for (const char of magazine) {
        ransomNote = ransomNote.replace(char, "");
    }
    return ransomNote.length === 0;
};

This works but is O(n * m) — replace scans the string each time. Fine for short strings, not great at scale.

The better approach

Use a frequency map:

var canConstruct = function(ransomNote, magazine) {
    const counts = {};

    for (const char of magazine) {
        counts[char] = (counts[char] || 0) + 1;
    }

    for (const char of ransomNote) {
        if (!counts[char] || counts[char] === 0) return false;
        counts[char]--;
    }

    return true;
};

Complexity

Frequency map approach:

• Time: O(n + m) — one pass through each string.
• Space: O(1) — the map holds at most 26 entries (lowercase English letters).

Replace approach:

• Time: O(n * m) — each replace call scans the remaining string.
• Space: O(n) — string immutability means new strings are created.

Trade-offs

The replace approach is fewer lines of code and easy to read. The frequency map is the proper solution — it's what an interviewer expects. In production, string manipulation with replace in a loop is a red flag for performance.