Ransom Note - Practice Coding Problems

Ransom Note - 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.

Input & Output

Example 1 — Basic Case

$ Input: ransomNote = "a", magazine = "b"

› Output: false

💡 Note: Magazine doesn't contain the letter 'a', so ransom note cannot be constructed

Example 2 — Sufficient Letters

$ Input: ransomNote = "aa", magazine = "aab"

› Output: true

💡 Note: Magazine contains 2 'a's and 1 'b', which is enough to construct "aa"

Example 3 — Insufficient Letters

$ Input: ransomNote = "aab", magazine = "baa"

› Output: true

💡 Note: Magazine has 2 'a's and 1 'b', exactly what we need for "aab"

Constraints

1 ≤ ransomNote.length, magazine.length ≤ 10⁵
ransomNote and magazine consist of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

Ransom note and magazine strings

Process

Check if magazine has enough letters

Output

True if construction possible, false otherwise

Key Takeaway

🎯 Key Insight: Count magazine letters first, then verify ransom note doesn't exceed available counts

Asked in

a Amazon 15 f Facebook 8

The key insight is to count the frequency of characters in the magazine first, then verify if we have enough characters to construct the ransom note. The optimal approach uses a hash map to achieve O(n + m) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Search and Mark	O(n×m)	O(m)	For each letter in ransom note, search through magazine and mark used letters
Frequency Count - Hash Map	O(n + m)	O(k)	Count letters in magazine, then check if ransom note requirements can be satisfied

Brute Force - Search and Mark — Algorithm Steps

Convert magazine to a list for modification
For each character in ransom note, search for it in magazine
If found, remove it from magazine; if not found, return false
If all characters found, return true

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Copy magazine letters to modify

For each ransom letter, find in magazine

Result

Return true if all letters found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* ransomNote, char* magazine) {
    int magLen = strlen(magazine);
    bool used[magLen];
    memset(used, false, sizeof(used));
    
    for (int i = 0; i < strlen(ransomNote); i++) {
        bool found = false;
        for (int j = 0; j < magLen; j++) {
            if (!used[j] && magazine[j] == ransomNote[i]) {
                used[j] = true;
                found = true;
                break;
            }
        }
        if (!found) return false;
    }
    
    return true;
}

int main() {
    char ransomNote[1000], magazine[1000];
    fgets(ransomNote, sizeof(ransomNote), stdin);
    fgets(magazine, sizeof(magazine), stdin);
    
    ransomNote[strcspn(ransomNote, "\n")] = 0;
    magazine[strcspn(magazine, "\n")] = 0;
    
    bool result = solution(ransomNote, magazine);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

For each character in ransom note (n), we scan through magazine (m)

✓ Linear Growth

Space Complexity

O(m)

Create a copy of magazine as a list for modifications

✓ Linear Space

156.0K Views

High Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Search and Mark — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler