Ransom Note

Problem Description

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true


This problem is to check whether magazine contains all char in ransomNote,

  • if magazine contains all characters in ransomNote, then true

  • otherwise any character in ransomNote but not in magazine, return false.

Using Map to keep char and frequency as pair in map.

  • Iterate magazine characters, add characters and frequency into map

  • Iterate ransomNote, check each character, if not exist in map or current frequency in map <= 0, then return false. otherwise continue.

  • For each visit, in map, put frequency - 1 back into map, continue

  • when done iterate ransomNote, all chars in map (in magazine)

For example:

Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(N)

  • N - Max (ransom note length, magazine length)


class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote == null || ransomNote == null && magazine == null) return true;
        if (magazine == null) return false;

        Map<Character, Integer> map = new HashMap<>();
        for (char ch : magazine.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        for (char ch : ransomNote.toCharArray()) {
            if (!map.containsKey(ch) || map.get(ch) <= 0) return false;
            map.put(ch, map.get(ch) - 1);

        return true;

Last updated