234. Ransom Note

Count how many of each letter the magazine provides. Then spend those letters on the ransom note — if any letter runs out, the note can't be built.

Idea

Building the note is possible exactly when the magazine has at least as many of every letter as the note needs. So tally the magazine's letters once, then walk the note decrementing counts; if a needed letter is already exhausted, the answer is false.

Algorithm

1. Build a count of each character in magazine.
2. For each character c in ransomNote: if counts[c] <= 0, return false; otherwise decrement counts[c].
3. If we finish, return true.

Worked example: ransomNote = "aab", magazine = "baa"

Counts of magazine: a:2, b:1. Spend for the note: a (a:1), a (a:0), b (b:0). Never went negative → true.

Contrast note "aa", magazine "ab": a:1. First a → a:0; second a → already 0 → false.

Complexity

• Time: O(m + n) over the two string lengths.
• Space: O(1) — at most 26 letters.

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