Log inSign up
easyleetcodeNot Started

Ransom Note

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

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 · Example:

Input: ransomNote = "a", magazine = "b"
Output: false
Explanation: magazine does not contain "a".

Example 2 · Example:

Input: ransomNote = "aa", magazine = "ab"
Output: false
Explanation: magazine contains one "a", but two are required.

Example 3 · Example:

Input: ransomNote = "aa", magazine = "aab"
Output: true
Explanation: magazine contains two "a"s, sufficient for ransomNote.

Constraints:

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote and magazine consist of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement resource consumption checks using frequency counts.
  • Optimize memory to O(1) using fixed-size alphabet arrays.
  • Apply early-exit length guards.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Determining if a string can be formed from an available supply of characters.
  • Multi-set subset verification.

Algorithmic Decision Tree:

  • Frequency Bucket Decrement
  • Resource Consumption

Connected Patterns:

Valid AnagramGroup AnagramsFind the Difference

1. Linear Search and Replace

Intuition

Iterate through each character in ransomNote. Find its first index in magazine. If not found, return false. If found, remove it from magazine and continue. Return true.

When to apply: Basic baseline comparison.

Algorithm

  1. If ransomNote.length > magazine.length: return false.
  2. Convert magazine to a mutable structure.
  3. For c in ransomNote:
  4. Find index of c in magazine.
  5. If not found: return false.
  6. Erase character at index from magazine.
  7. Return true.

Linear Search and Character Removal Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a]
Current operationSTEP 1 OF 6
Observation: Find first 'a' in magazine
Visual state
Values and pointers at this exact step
array
S
a
a
0
1
Variables at this step
Char
'a'
Magazine After
ab
Check / comparison
Search for ransomNote[0]='a' in magazine ("aab"). Found at index 0.
Decision / next transition
Consume 'a' from magazine: remove index 0. Magazine becomes "ab".
Why this step matters

Observation: Find first 'a' in magazine.

Decision: Match found at index 0. Remove it so it cannot be reused.

Invariant: One 'a' fulfilled; magazine reduces to "ab".

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 bool canConstruct(std::string ransomNote, std::string magazine) {
7 if (ransomNote.size() > magazine.size()) return false;
8 for (char c : ransomNote) {
9 size_t pos = magazine.find(c);
10 if (pos == std::string::npos) return false;
11 magazine.erase(pos, 1);
12 }
13 return true;
14 }
15};
16
17int main() {
18 Solution sol;
19 std::cout << (sol.canConstruct("a", "b") ? "true" : "false") << std::endl; // false
20 std::cout << (sol.canConstruct("aa", "aab") ? "true" : "false") << std::endl; // true
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(N * M) — N searches, each scanning through M characters.
  • Space complexity: O(M)

Why Brute Force Doesn't Scale:

On-the-fly decrementing terminates on first violation.

26-integer stack array.

2. Hash Map Counting

Intuition

Build a hash map of character counts in magazine. For each character in ransomNote, decrement its count in the map. If the count is 0 or character is missing, return false.

When to apply: When inputs contain arbitrary non-ASCII characters.

Algorithm

  1. If ransomNote.length > magazine.length: return false.
  2. Initialize map = {}.
  3. For c in magazine: map[c] = (map[c] || 0) + 1.
  4. For c in ransomNote:
  5. If !map[c] || map[c] == 0: return false.
  6. map[c]--.
  7. Return true.

Hash Map Frequency Counting Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b]
Current operationSTEP 1 OF 6
Observation: Scan magazine = "aab"
Visual state
Values and pointers at this exact step
array
S
a:2
b:1
0
↑ TALLY MAGAZINE
1
Variables at this step
Inventory
{"a":2,"b":1}
Check / comparison
Count frequencies in magazine = "aab": { 'a': 2, 'b': 1 }.
Decision / next transition
Store character counts in hash map.
Why this step matters

Observation: Scan magazine = "aab".

Decision: Populate frequency map: 'a': 2, 'b': 1.

Invariant: Available inventory recorded.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4
5class Solution {
6public:
7 bool canConstruct(std::string ransomNote, std::string magazine) {
8 if (ransomNote.size() > magazine.size()) return false;
9 std::unordered_map<char, int> counts;
10 for (char c : magazine) counts[c]++;
11 for (char c : ransomNote) {
12 if (--counts[c] < 0) return false;
13 }
14 return true;
15 }
16};
17
18int main() {
19 Solution sol;
20 std::cout << (sol.canConstruct("aa", "aab") ? "true" : "false") << std::endl; // true
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(N + M) — Single linear pass over magazine and ransomNote.
  • Space complexity: O(U) where U <= 26

3. Fixed 26-Element Array (Optimal)

Intuition

Check if (ransomNote.length > magazine.length) return false;. Initialize count[26] = 0. For each character c in magazine, increment count[c - 'a']++. For each character c in ransomNote, decrement count[c - 'a']--. If count[c - 'a'] < 0, return false. If loop finishes, return true.

When to apply: The standard gold standard solution.

Algorithm

  1. If ransomNote.length > magazine.length: return false.
  2. Initialize count = new int[26].
  3. For c in magazine: count[c - 'a']++.
  4. For c in ransomNote:
  5. If --count[c - 'a'] < 0: return false.
  6. Return true.

Magazine Inventory Consumption Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a, b]
Current operationSTEP 1 OF 6
Observation: Scan magazine to build character frequency count
Visual state
Values and pointers at this exact step
array
S
a
a
b
0
↑ mag[0]: 'a'
1
2
Variables at this step
Phase
Count Magazine
Char
a
Inventory
{ a: 1 }
Check / comparison
Build magazine frequency table: add 'a'.
Decision / next transition
counts['a'] = 1.
Why this step matters

Observation: Scan magazine to build character frequency count. First character is 'a'.

Decision: Increment count of 'a' in frequency table to 1.

Invariant: Magazine inventory counts available character supply.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 bool canConstruct(std::string ransomNote, std::string magazine) {
7 if (ransomNote.size() > magazine.size()) return false;
8 int count[26] = {0};
9 for (char c : magazine) count[c - 'a']++;
10 for (char c : ransomNote) {
11 if (--count[c - 'a'] < 0) return false;
12 }
13 return true;
14 }
15};
16
17int main() {
18 Solution sol;
19 std::cout << (sol.canConstruct("a", "b") ? "true" : "false") << std::endl; // false
20 std::cout << (sol.canConstruct("aa", "ab") ? "true" : "false") << std::endl; // false
21 std::cout << (sol.canConstruct("aa", "aab") ? "true" : "false") << std::endl; // true
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(N + M) strictly — Linear pass over both strings with stack-allocated constant array.
  • Space complexity: O(1) extra space (26 integers)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Search and Delete (Brute Force)O(N * M)O(M)Finds and erases characters one by one.Quadratic time complexity.
2.Hash Map CountingO(N + M)O(U) unique charactersHandles Unicode or non-ASCII characters.Hash table boxing overhead.
3.Fixed 26-Array Counting (Optimal)OptimalO(N + M)O(1) extra spaceMaximum cache locality, zero heap allocation, early exit.Limited to lowercase English alphabet.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not performing the ransomNote.length > magazine.length fast guard.

Pitfall 2:

Counting ransomNote first and checking against magazine (requires full count verification rather than early break).

Crucial Edge Cases to Validate:

  • ransomNote longer than magazine: Length check returns false in O(1).
  • Single character match (ransomNote = a, magazine = a): count[a] becomes 0, returns true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the initial length guard ransomNote.length > magazine.length.
  2. Show why the fixed 26-array is cache-friendly and O(1) space.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is counting the magazine and decrementing with ransomNote more optimal than counting both?

Back to DSA Sheet