Code Logo

Ransom Note

Published at16 Mar 2026
Created by
Easy 21 views
Like0

You are given two strings: the ransom note you want to build and the magazine you are allowed to cut letters from.

Each character in the magazine can be used at most once. That means it is not enough for a letter to exist somewhere in the magazine; it has to exist enough times to cover the note.

For example, ransomNote = "a" and magazine = "b" returns false because the needed letter does not exist. ransomNote = "aa" and magazine = "ab" is also false because there is only one 'a'. But ransomNote = "aa" and magazine = "aab" returns true.

So the question is whether the magazine has enough copies of every character required by the note.

Example Input & Output

Example 1
Input
ransomNote = "a", magazine = "b"
Output
false
Explanation

The needed character does not exist in magazine.

Example 2
Input
ransomNote = "aa", magazine = "ab"
Output
false
Explanation

There is only one a available.

Example 3
Input
ransomNote = "aa", magazine = "aab"
Output
true
Explanation

The magazine provides enough characters.

Algorithm Flow

Recommendation Algorithm Flow for Ransom Note

Solution Approach

Determine if a ransom note can be constructed from the letters available in a magazine. Each letter in the magazine can be used at most once. Count the frequency of each character in the magazine, then decrement counts for each character needed in the ransom note. If any character runs out, the note cannot be constructed.

function canConstruct(ransomNote, magazine) {
  var freq = {};
  for (var i = 0; i < magazine.length; i++) {
    freq[magazine[i]] = (freq[magazine[i]] || 0) + 1;
  }
  for (var i = 0; i < ransomNote.length; i++) {
    if (!freq[ransomNote[i]]) return false;
    freq[ransomNote[i]]--;
  }
  return true;
}

First pass counts magazine letters. Second pass checks ransom note letters against available counts. If a letter is missing or exhausted, return false. The magazine supplies a limited pool of each character that can be spent by the note.

Time complexity is O(M + R), space complexity is O(k) where k is the alphabet size (26 for lowercase).

Best Answers

java
import java.util.*;
class Solution {
    public boolean ransom_note(String ransomNote, String magazine) {
        Map<Character, Integer> count = new HashMap<>();
        for (char ch : magazine.toCharArray()) count.put(ch, count.getOrDefault(ch, 0) + 1);
        for (char ch : ransomNote.toCharArray()) {
            if (!count.containsKey(ch) || count.get(ch) == 0) return false;
            count.put(ch, count.get(ch) - 1);
        }
        return true;
    }
}