Ransom Note

Easy
214.

Ransom Note

Ransom Note is an easy coding problem on strings, hash table and counting, asked in Amazon, Infosys, Bloomberg and Apple interviews.

Given two strings ransomNote and magazine, return true if ransomNote can be built using the letters of magazine.

Each letter of magazine may be used at most once.

Example 1

Input
ransomNote = "a", magazine = "b"
Output
false

Example 2

Input
ransomNote = "aa", magazine = "ab"
Output
false
Explanation
The magazine has only one a.

Example 3

Input
ransomNote = "aa", magazine = "aab"
Output
true

Constraints

  • 1 <= ransomNote.length, magazine.length <= 40
  • Both consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Ransom Note — Solution in Python, Java & C++

Ransom Note solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Infosys.

Ransom Note is an easy coding problem on strings, hash table and counting, asked in Amazon, Infosys, Bloomberg and Apple interviews.

Problem statement

Given two strings ransomNote and magazine, return true if ransomNote can be built using the letters of magazine.

Each letter of magazine may be used at most once.

Example 1

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2

Input: ransomNote = "aa", magazine = "ab"
Output: false
Explanation: The magazine has only one a.

Example 3

Input: ransomNote = "aa", magazine = "aab"
Output: true

Constraints

  • 1 <= ransomNote.length, magazine.length <= 40
  • Both consist of lowercase English letters.

Hints for Ransom Note

  1. Hint 1

    Count what the magazine supplies, then spend from those counts as you read the note.

  2. Hint 2

    The moment a count would go negative, the magazine cannot cover the note.

How to solve Ransom Note

Count what the magazine supplies, then spend those counts while reading the note; a count going negative means the magazine cannot cover it.

Approach

  1. Tally each letter of magazine.
  2. For each letter of ransomNote, decrement its count and return false if it drops below zero.
  3. Return true.

Why it works

Each letter of the magazine can be used once, so the tally is a budget; the note is buildable exactly when no letter's demand exceeds its budget.

Complexity

  • Time — O(n + m)
  • Space — O(1) — 26 counters

Pitfalls

  • An early length check (len(note) > len(magazine) → false) is a cheap short-circuit.

Reference solution

Python

def canConstruct(ransomNote: str, magazine: str) -> bool:
    count = [0] * 26
    for ch in magazine:
        count[ord(ch) - 97] += 1
    for ch in ransomNote:
        idx = ord(ch) - 97
        count[idx] -= 1
        if count[idx] < 0:
            return False
    return True

Java

public static boolean canConstruct(String ransomNote, String magazine) {
    int[] count = new int[26];
    for (int i = 0; i < magazine.length(); i++) count[magazine.charAt(i) - 'a']++;
    for (int i = 0; i < ransomNote.length(); i++) {
        int idx = ransomNote.charAt(i) - 'a';
        count[idx]--;
        if (count[idx] < 0) return false;
    }
    return true;
}

C++

bool canConstruct(string ransomNote, string magazine) {
    int count[26] = {0};
    for (char ch : magazine) count[ch - 'a']++;
    for (char ch : ransomNote) {
        int idx = ch - 'a';
        count[idx]--;
        if (count[idx] < 0) return false;
    }
    return true;
}

JavaScript

var canConstruct = function(ransomNote, magazine) {
    const count = new Array(26).fill(0);
    for (let i = 0; i < magazine.length; i++) count[magazine.charCodeAt(i) - 97]++;
    for (let i = 0; i < ransomNote.length; i++) {
        const idx = ransomNote.charCodeAt(i) - 97;
        count[idx]--;
        if (count[idx] < 0) return false;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets