Skip to main content

383. Ransom Note

easy

Given two strings ransomNote and magazine, decide whether ransomNote can be constructed from the letters of magazine (each letter used at most once). Drop-in letter-count problem — one of the gentlest hash-counting warm-ups in the catalog.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

  • 1 <= ransomNote.length, magazine.length <= 10^5
  • ransomNote and magazine 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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If ransomNote.length > magazine.length, immediate false.

Hint 2

Count letters in magazine; for each letter in ransomNote, decrement. If any count goes negative, return false.

Hint 3

For lowercase-only, a length-26 array is faster than a hash map with the same logic.

Solution approach

Reveal approach

If len(ransomNote) > len(magazine), return false. Build a length-26 count array from magazine: count[c - 'a'] += 1 for each char. Walk ransomNote: for each char, decrement count[c - 'a']; if it goes below 0, return false. If you finish the walk without going negative, return true. Single linear scan in each direction. O(n + m) time, O(1) space (26-entry array is constant). The hash-map version is the same algorithm with a dict; slightly slower constants. The 'len check first' is the cheap O(1) early-exit.

Complexity

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

Related patterns

  • hash-table
  • counting
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Ransom Note and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →