17. Ransom Note

easyAsked at Etsy

Determine whether a string can be built from the letters of another — Etsy uses this pattern to check if a listing title can be composed from a seller's available tag inventory.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

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

Constraints

1 <= ransomNote.length, magazine.length <= 10^5
ransomNote and magazine consist of lowercase English letters
Each letter in magazine may be used at most once

Examples

Example 1

Input

ransomNote = "aa", magazine = "aab"

Output

true

Example 2

Input

ransomNote = "aa", magazine = "ab"

Output

false

Approaches

1. Brute force

For each character in ransomNote, search and remove it from a mutable copy of magazine. O(n*m) because each search scans the magazine string.

Time: O(n*m)
Space: O(m)

function canConstruct(ransomNote, magazine) {
  let pool = magazine.split('');
  for (const ch of ransomNote) {
    const idx = pool.indexOf(ch);
    if (idx === -1) return false;
    pool.splice(idx, 1);
  }
  return true;
}

Tradeoff:

2. Frequency map

Count every character in magazine, then decrement counts as you consume ransomNote characters. If any count goes negative, return false immediately.

Time: O(n + m)
Space: O(1) — at most 26 keys

function canConstruct(ransomNote, magazine) {
  const freq = {};
  for (const ch of magazine) {
    freq[ch] = (freq[ch] || 0) + 1;
  }
  for (const ch of ransomNote) {
    if (!freq[ch]) return false;
    freq[ch]--;
  }
  return true;
}

Tradeoff:

Etsy-specific tips

Etsy sometimes reframes this as 'can a listing description be assembled from a seller's saved tag pool' — the frequency-map approach directly mirrors how tag inventory is audited at scale. Explain why the bounded alphabet makes space O(1).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Ransom Note and other Etsy interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →