383. Ransom Note

easyAsked at Duolingo

Check whether one string's characters can be constructed from another — the same character-budget check Duolingo's hint system runs to decide if a learner's remaining tile set can form the target phrase without reshuffling the tile pool.

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 by using the letters from magazine, and false otherwise. Each letter in magazine can only be used once.

Constraints

1 <= ransomNote.length, magazine.length <= 10^5
Both strings consist of lowercase English letters

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

Approaches

1. Brute force — sort and scan

Sort both strings and use two pointers to match each character of ransomNote against magazine.

Time: O(m log m + n log n)
Space: O(m + n)

function canConstruct(ransomNote, magazine) {
  const r = ransomNote.split('').sort();
  const m = magazine.split('').sort();
  let mi = 0;
  for (const ch of r) {
    while (mi < m.length && m[mi] < ch) mi++;
    if (mi >= m.length || m[mi] !== ch) return false;
    mi++;
  }
  return true;
}

Tradeoff:

2. Optimal — frequency array

Count magazine's characters in a 26-slot array, then consume counts for ransomNote — short-circuit as soon as any count goes negative.

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

function canConstruct(ransomNote, magazine) {
  const freq = new Array(26).fill(0);
  const a = 'a'.charCodeAt(0);
  for (const ch of magazine) freq[ch.charCodeAt(0) - a]++;
  for (const ch of ransomNote) {
    const idx = ch.charCodeAt(0) - a;
    if (--freq[idx] < 0) return false;
  }
  return true;
}

Tradeoff:

Duolingo-specific tips

Duolingo interviewers use this problem to see whether you immediately recognize it as a frequency-budget problem — essentially the same check powering the tile-game validation. The key interviewer signal they look for: early termination the moment a deficit appears rather than scanning the entire ransomNote. Mention the O(1) space bound because the alphabet is fixed; that detail resonates with engineers who work on constrained mobile vocabulary engines.

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 Duolingo interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →