Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine. Each letter in magazine can only be used once.

Examples

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^5
  • ransomNote and magazine consist of lowercase English letters

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Two pointers on string (this problem) O(n) O(1) Palindrome, parsing
Hash map / frequency O(n) O(k) Anagram, character counts
KMP / rolling hash O(n) O(n) Pattern matching
Stack parsing O(n) O(n) Decode string, parentheses

Thinking Process

This is a frequency counting problem: does magazine have enough of each character to build ransomNote?

Count character frequencies in magazine, then consume them for each character in ransomNote. If any count goes negative, the magazine doesn’t have enough of that letter.

Walk-Through: ransomNote = “aa”, magazine = “aab”

After scanning magazine:  a:2, b:1
Consume 'a' → a:1
Consume 'a' → a:0
All valid → return true
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Approach 1: Frequency Array – O(n + m) time, O(1) space

Since characters are lowercase letters, a 26-element array suffices.

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int count[26] = {0};

        for (char c : magazine)
            count[c - 'a']++;

        for (char c : ransomNote) {
            count[c - 'a']--;
            if (count[c - 'a'] < 0)
                return false;
        }

        return true;
    }
};

Solution Explanation

Approach: Two pointers on string (this problem)

Key idea: This is a frequency counting problem: does magazine have enough of each character to build ransomNote?

Walkthrough — input ransomNote = "a", magazine = "b", expected output false:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Approach 2: Hash Map – O(n + m) time, O(k) space

Generalizes to any character set.

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;
    }
};

Time: O(n + m) Space: O(k) where k is the number of distinct characters

Common Mistakes

  • Counting ransomNote instead of magazine first (need to build the supply before consuming)
  • Forgetting the early exit on negative count (checking only at the end misses efficiency)

Key Takeaways

  • Same frequency counting pattern as LC 242 Valid Anagram, but one-directional: magazine supplies letters, ransom note consumes them
  • The array solution is preferred in interviews: faster, constant space, simpler
  • This is a “is A a subset of B (with multiplicity)” check

References

Template Reference