383. Ransom Note - Solution & Explanation

Q: Is Ransom Note easy or hard?

Ransom Note is classified as an Easy problem with an acceptance rate around 65%. The challenge focuses on recognizing that character frequency counting eliminates the need for repeated searches, enabling a simple linear-time solution.

Q: Ransom Note Python/Java solution

In Python, developers typically use a dictionary or a list of 26 integers to store character frequencies. In Java, a HashMap or an int[26] array is common. Both implementations follow the same logic: count magazine characters, then decrement counts while scanning the ransom note.

The problem

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

Each letter in magazine can only be used once in ransomNote.

Example 1:

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

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

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

Constraints:

1 <= ransomNote.length, magazine.length <= 10⁵
ransomNote and magazine consist of lowercase English letters.

Approach overview

Problem Overview: You are given two strings: ransomNote and magazine. Determine whether the ransom note can be constructed using letters from the magazine. Each character in magazine can only be used once, so you must verify that the magazine contains at least the same frequency of every character required by the ransom note.

Approach 1: Frequency Counting with Hash Maps (Time: O(n + m), Space: O(1))

This method counts how many times each character appears in the magazine, then checks whether the ransom note can consume those counts. First iterate through magazine and store frequencies in a hash map or fixed-size array for lowercase letters. Then iterate through ransomNote, decrementing the count for each character. If any count becomes negative or missing, the note cannot be constructed. The key insight: verifying character availability is a constant-time hash lookup instead of repeatedly scanning the string.

Because the alphabet is limited (26 lowercase letters), the auxiliary space is effectively constant. This approach runs in linear time relative to the combined lengths of both strings. It’s the most direct solution using hash tables and frequency counting, and it works well for any string size.

Approach 2: Sorting and Two Pointers (Time: O(n log n + m log m), Space: O(1) or O(n))

This strategy sorts both strings first. After sorting, traverse them using two pointers. One pointer scans the sorted magazine string while the other tracks characters in ransomNote. When characters match, advance both pointers since the letter is successfully used. If the magazine character is smaller, advance only the magazine pointer. If the ransom note character is smaller, construction is impossible because the required letter does not exist ahead.

The sorted ordering groups identical characters together, which makes comparison straightforward without a hash map. However, sorting introduces an O(n log n) cost, making it slower than the counting approach for large inputs. This method mainly demonstrates pointer techniques on sorted string data.

Recommended for interviews: Frequency counting with a hash map or fixed array is the expected answer. It runs in linear time and directly models the constraint that each magazine letter can only be used once. Interviewers often accept either a hash map or a 26-length integer array. Explaining the sorting approach shows awareness of alternative strategies, but the O(n) counting solution demonstrates stronger algorithmic judgment.

Approach 1: Approach 1: Frequency Counting with Hash Maps

This approach involves using hash maps to count the frequency of each letter in both ransomNote and magazine. The idea is to determine if magazine has enough of each letter to build ransomNote.

Create a frequency count for each letter in magazine.
Iterate over each letter in ransomNote and check if the magazine frequency is sufficient.
If any letter in ransomNote has a higher frequency than in magazine, return false.
If all letters are accounted for, return true.

Python

from collections import Counter

def canConstruct(ransomNote: str, magazine: str) -> bool:
    magazine_count = Counter(magazine)
    ransom_count = Counter(ransomNote)
    for char, count in ransom_count.items():
        if magazine_count[char] < count:
            return False
    return True

Java

import java.util.HashMap;

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> count = new HashMap<>();
        for (char c : magazine.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
        }
        for (char c : ransomNote.toCharArray()) {
            if (count.getOrDefault(c, 0) <= 0) {
                return false;
            }
            count.put(c, count.get(c) - 1);
        }
        return true;
    }
}

C++

#include <unordered_map>
#include <string>
using namespace std;

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> count;
        for (char c : magazine) {
            count[c]++;
        }
        for (char c : ransomNote) {
            if (count[c]-- <= 0) {
                return false;
            }
        }
        return true;
    }
};

JavaScript

var canConstruct = function(ransomNote, magazine) {
    let count = {};
    for (let char of magazine) {
        count[char] = (count[char] || 0) + 1;
    }
    for (let char of ransomNote) {
        if (!count[char] || count[char] <= 0) return false;
        count[char]--;
    }
    return true;
};

#include <stdbool.h>
#include <string.h>

bool canConstruct(char * ransomNote, char * magazine) {
    int count[26] = {0};
    for (int i = 0; magazine[i]; i++) {
        count[magazine[i] - 'a']++;
    }
    for (int i = 0; ransomNote[i]; i++) {
        if (--count[ransomNote[i] - 'a'] < 0) {
            return false;
        }
    }
    return true;
}

using System;
using System.Collections.Generic;

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        Dictionary<char, int> count = new Dictionary<char, int>();
        foreach (char c in magazine) {
            if (count.ContainsKey(c)) count[c]++;
            else count[c] = 1;
        }
        foreach (char c in ransomNote) {
            if (!count.ContainsKey(c) || count[c] <= 0) return false;
            count[c]--;
        }
        return true;
    }
}

Python's Counter from the collections module provides an elegant way to count frequencies. The solution compares the counters of ransomNote and magazine to determine constructibility.

Complexity

Time Complexity: O(m + n)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Approach 2: Sorting and Two Pointers

Instead of counting character frequencies, we can sort both ransomNote and magazine and use a two-pointer technique to check if magazine contains all letters needed for ransomNote in a sorted order.

Sort the characters in both ransomNote and magazine.
Initialize two pointers, one for each string.
Iterate through the sorted strings using the pointers. If the characters match, move both pointers forward.
If all characters in ransomNote are matched, return true; otherwise, return false.

Python

def canConstruct(ransomNote: str, magazine: str) -> bool:
    ransomNote = sorted(ransomNote)
    magazine = sorted(magazine)
    i, j = 0, 0
    while i < len(ransomNote) and j < len(magazine):
        if ransomNote[i] == magazine[j]:
            i += 1
        j += 1
    return i == len(ransomNote)

Java

import java.util.Arrays;

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] ransomArray = ransomNote.toCharArray();
        char[] magazineArray = magazine.toCharArray();
        Arrays.sort(ransomArray);
        Arrays.sort(magazineArray);
        int i = 0, j = 0;
        while (i < ransomArray.length && j < magazineArray.length) {
            if (ransomArray[i] == magazineArray[j]) {
                i++;
            }
            j++;
        }
        return i == ransomArray.length;
    }
}

C++

#include <algorithm>
#include <string>
using namespace std;

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        sort(ransomNote.begin(), ransomNote.end());
        sort(magazine.begin(), magazine.end());
        int i = 0, j = 0;
        while (i < ransomNote.length() && j < magazine.length()) {
            if (ransomNote[i] == magazine[j]) {
                i++;
            }
            j++;
        }
        return i == ransomNote.length();
    }
};

JavaScript

var canConstruct = function(ransomNote, magazine) {
    ransomNote = ransomNote.split('').sort();
    magazine = magazine.split('').sort();
    let i = 0, j = 0;
    while (i < ransomNote.length && j < magazine.length) {
        if (ransomNote[i] === magazine[j]) {
            i++;
        }
        j++;
    }
    return i === ransomNote.length;
};

#include <stdbool.h>
#include <string.h>

int cmpfunc(const void *a, const void *b) {
    return (*(char *)a - *(char *)b);
}

bool canConstruct(char *ransomNote, char *magazine) {
    int n = strlen(ransomNote);
    int m = strlen(magazine);
    qsort(ransomNote, n, sizeof(char), cmpfunc);
    qsort(magazine, m, sizeof(char), cmpfunc);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (ransomNote[i] == magazine[j]) {
            i++;
        }
        j++;
    }
    return i == n;
}

using System;

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        char[] ransomArray = ransomNote.ToCharArray();
        char[] magArray = magazine.ToCharArray();
        Array.Sort(ransomArray);
        Array.Sort(magArray);
        int i = 0, j = 0;
        while (i < ransomArray.Length && j < magArray.Length) {
            if (ransomArray[i] == magArray[j]) {
                i++;
            }
            j++;
        }
        return i == ransomArray.Length;
    }
}

The Python implementation sorts the characters in both strings and uses an iterative two-pointer method to confirm that each character required by ransomNote exists in magazine.

Complexity

Time Complexity: O(n log n + m log m), for sorting each string
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Hash Table or Array

We can use a hash table or an array cnt of length 26 to record the number of times each character appears in the string magazine. Then traverse the string ransomNote, for each character c in it, we decrease the number of c by 1 in cnt. If the number of c is less than 0 after the decrease, it means that the number of c in magazine is not enough, so it cannot be composed of ransomNote, just return false.

Otherwise, after the traversal, it means that each character in ransomNote can be found in magazine. Therefore, return true.

The time complexity is O(m + n), and the space complexity is O(C). Where m and n are the lengths of the strings ransomNote and magazine respectively; and C is the size of the character set, which is 26 in this question.

TypeScript

function canConstruct(ransomNote: string, magazine: string): boolean {
    const cnt: number[] = Array(26).fill(0);
    for (const c of magazine) {
        ++cnt[c.charCodeAt(0) - 97];
    }
    for (const c of ransomNote) {
        if (--cnt[c.charCodeAt(0) - 97] < 0) {
            return false;
        }
    }
    return true;
}

func canConstruct(ransomNote string, magazine string) bool {
	cnt := [26]int{}
	for _, c := range magazine {
		cnt[c-'a']++
	}
	for _, c := range ransomNote {
		cnt[c-'a']--
		if cnt[c-'a'] < 0 {
			return false
		}
	}
	return true
}

PHP

class Solution {
    /**
     * @param String $ransomNote
     * @param String $magazine
     * @return Boolean
     */
    function canConstruct($ransomNote, $magazine) {
        $arrM = str_split($magazine);
        for ($i = 0; $i < strlen($magazine); $i++) {
            $hashtable[$arrM[$i]] += 1;
        }
        for ($j = 0; $j < strlen($ransomNote); $j++) {
            if (!isset($hashtable[$ransomNote[$j]]) || $hashtable[$ransomNote[$j]] == 0) {
                return false;
            } else {
                $hashtable[$ransomNote[$j]] -= 1;
            }
        }
        return true;
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Frequency Counting with Hash Maps	Time Complexity: O(m + n) Space Complexity: O(1)
Approach 2: Sorting and Two Pointers	Time Complexity: O(n log n + m log m), for sorting each string Space Complexity: O(1)
Hash Table or Array	–

Complexity analysis

Approach	Time	Space	When to Use
Frequency Counting with Hash Map	O(n + m)	O(1)	General case. Fastest solution when checking character availability.
Sorting and Two Pointers	O(n log n + m log m)	O(1) or O(n)	Useful when data is already sorted or when practicing two-pointer techniques.

Frequently asked questions

Is Ransom Note easy or hard?

Ransom Note is classified as an Easy problem with an acceptance rate around 65%. The challenge focuses on recognizing that character frequency counting eliminates the need for repeated searches, enabling a simple linear-time solution.

Ransom Note Python/Java solution

In Python, developers typically use a dictionary or a list of 26 integers to store character frequencies. In Java, a HashMap<Character, Integer> or an int[26] array is common. Both implementations follow the same logic: count magazine characters, then decrement counts while scanning the ransom note.

How to solve Ransom Note in O(n)?

Iterate through the magazine and count character frequencies using a hash map or a 26-element integer array. Then iterate through the ransom note and decrease the corresponding counts. If any character count drops below zero, the ransom note cannot be constructed. Each operation is constant time, giving an overall O(n + m) solution.

What is the best approach for Ransom Note?

The best approach uses frequency counting with a hash map or a fixed array of size 26. Count how many times each character appears in the magazine, then decrement counts while scanning the ransom note. If any required character is unavailable, return false. This method runs in O(n + m) time and O(1) space.

Is Ransom Note asked at Google/Amazon/Meta?

Ransom Note is a common easy-level interview problem and has appeared in coding interviews and online assessments at companies like Amazon and Meta. It tests understanding of hash maps, frequency counting, and basic string manipulation—skills frequently evaluated in early interview rounds.

What data structure is used in Ransom Note?

The typical data structure is a hash table or a fixed-size frequency array. These structures store the count of each character in the magazine and allow constant-time updates and lookups while processing the ransom note.

What is the time complexity of Ransom Note?

The optimal solution runs in O(n + m) time, where n is the length of the magazine and m is the length of the ransom note. Each string is scanned once while performing constant-time hash lookups or array updates. Space complexity is O(1) because only 26 character counts are stored.

Ransom Note solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Frequency Counting with Hash Maps

Approach 2: Approach 2: Sorting and Two Pointers

Approach 3: Hash Table or Array

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Ransom Note solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Frequency Counting with Hash Maps

Approach 2: Approach 2: Sorting and Two Pointers

Approach 3: Hash Table or Array

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems