Ransom Note - Leetcode Solution

Problem Link

Step-by-Step Thought Process

Brute Force

Understand the Problem:
- We are given two strings: ransomNote and magazine.
- We need to determine if we can use the letters from magazine to form the ransomNote.
- Each letter in the ransomNote must appear in magazine with the same frequency or higher.
Loop Through RansomNote:
- For every letter in ransomNote, check if it exists in magazine.
Find the Letter in Magazine:
- If the letter exists in magazine, remove it by slicing the string (we assume each letter can only be used once).
- If a letter is not found, return False immediately.
Return True:
- If all letters in the ransomNote can be found and removed from magazine, return True.

Code Solution (Brute Force)

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        for letter in ransomNote:
            if letter in magazine:
                position = magazine.index(letter)
                magazine = magazine[:position] + magazine[position+1:]
            else:
                return False

        return True
# Time: O(R * M)
# Space: O(1)

#include <string>
using namespace std;

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for (char letter : ransomNote) {
            size_t pos = magazine.find(letter);
            if (pos != string::npos) {
                magazine.erase(pos, 1);
            } else {
                return false;
            }
        }
        return true;
    }
};
// Time: O(R * M)
// Space: O(1) (ignoring the cost of string copy operations)

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        for (int i = 0; i < ransomNote.length(); i++) {
            char letter = ransomNote.charAt(i);
            int index = magazine.indexOf(letter);
            if (index != -1) {
                magazine = magazine.substring(0, index) + magazine.substring(index + 1);
            } else {
                return false;
            }
        }
        return true;
    }
}
// Time: O(R * M)
// Space: O(1) (new strings are created each time due to immutability)

var canConstruct = function(ransomNote, magazine) {
    for (let i = 0; i < ransomNote.length; i++) {
        let letter = ransomNote[i];
        let index = magazine.indexOf(letter);
        if (index !== -1) {
            magazine = magazine.slice(0, index) + magazine.slice(index + 1);
        } else {
            return false;
        }
    }
    return true;
};
// Time: O(R * M)
// Space: O(1) (magazine string reassignments consume additional memory implicitly)

Why the Brute Force Solution is Inefficient

The brute force solution is inefficient because it repeatedly searches for each character of the ransomNote in the magazine, which takes O(M) time for each letter. This leads to a total time complexity of O(R * M), which becomes slow as the input size grows. Additionally, slicing the string every time we remove a character introduces overhead.

💡 Optimal Solution: Improving Efficiency

To fix the inefficiency, we use a hashmap (or a Counter) to count the frequency of characters in magazine, which allows us to check the availability of each character in constant time. Here's the process:

Optimal Solution Step-by-Step:

Count the Frequency of Characters in Magazine:
- First, we create a hashmap (or use Counter) to store the frequency of each character in the magazine.
- This step takes O(M) time, where M is the length of the magazine.
Check for Each Character in RansomNote:
- For each character in the ransomNote, check if it exists in the hashmap with a positive frequency.
- If the character exists, decrease the count in the hashmap.
- If the character doesn't exist or its frequency is 0, return False.
Return True:
- If we successfully process all the characters in ransomNote, return True.

Code Solution (Optimal)

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        hashmap = Counter(magazine) # TC for Counter is O(n)

        for ch in ransomNote:
            if hashmap[ch] > 0:
                hashmap[ch]-=1
            else:
                return False
        return True

# Time Complexity: O(R + M)  -> R = len(ransomNote), M = len(magazine)
# Space Complexity: O(M)     -> we're using a hashmap

#include <unordered_map>
#include <string>
using namespace std;

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> hashmap;

        for (char ch : magazine) {
            hashmap[ch]++;
        }

        for (char ch : ransomNote) {
            if (hashmap[ch] > 0) {
                hashmap[ch]--;
            } else {
                return false;
            }
        }

        return true;
    }
};

// Time Complexity: O(m + n)  -> m = length of ransomNote, n = length of magazine
// Space Complexity: O(n)     -> we're using an unordered_map

import java.util.HashMap;

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> hashmap = new HashMap<>(); 
        
        for (char ch : magazine.toCharArray()) {
            hashmap.put(ch, hashmap.getOrDefault(ch, 0) + 1);
        }

        for (char ch : ransomNote.toCharArray()) {
            if (hashmap.getOrDefault(ch, 0) > 0) {
                hashmap.put(ch, hashmap.get(ch) - 1);
            } else {
                return false;
            }
        }
        
        return true;
    }
}

// Time Complexity: O(m + n)  -> m = len(ransomNote), n = len(magazine)
// Space Complexity: O(n)     -> we're using a hashmap

var canConstruct = function(ransomNote, magazine) {
    let hashmap = {}; 

    for (let ch of magazine) {
        hashmap[ch] = (hashmap[ch] || 0) + 1;
    }

    for (let ch of ransomNote) {
        if (hashmap[ch] > 0) {
            hashmap[ch]--;
        } else {
            return false;
        }
    }

    return true;
};

// Time Complexity: O(m + n)  -> m = length of ransomNote, n = length of magazine
// Space Complexity: O(n)     -> we're using a hashmap

Detailed Explanation

Understanding the Problem: Ransom Note

The “Ransom Note” problem is a common string manipulation task. You are given two strings: ransomNote and magazine. The goal is to determine whether you can construct the ransomNote by using letters from the magazine string. Each letter in magazine can only be used once.

For example:

Input: ransomNote = "a", magazine = "b" → Output: false
Input: ransomNote = "aa", magazine = "aab" → Output: true

Why This Problem Matters

This problem is important because it reflects real-world scenarios like checking resource availability, verifying data integrity, or solving subset containment problems. It also introduces essential concepts like character counting, frequency analysis, and hash maps — all of which are frequently used in string and array processing tasks.

Brute Force Approach

The brute-force method involves checking, for every character in ransomNote, whether it exists in magazine. If it does, we remove that character from magazine (to simulate using it once). If any character is not found, we return false.

This approach leads to poor performance because searching for a character in a string is O(M), and we do this for each character in ransomNote. The total time complexity becomes O(R × M), which is inefficient for longer strings.

Optimized Solution: Use a Hash Map (Counter)

The optimal way to solve this problem is by using a hash map (or Python’s collections.Counter) to count how many times each character appears in magazine. This allows for fast and efficient lookups while processing ransomNote.

Step-by-Step Plan

Count Frequency of Characters in Magazine:
Loop through each character in magazine and record how many times it appears. This takes O(M) time.
Check Characters in Ransom Note:
For every character in ransomNote, check if it exists in the hash map and whether its count is positive.
Update the Hash Map:
If the character is available, decrease its count. If it's not available or the count is zero, return false.
Return True:
If all characters in ransomNote are accounted for, return true.

Example Walkthrough

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

Build frequency map from magazine: {'b': 1, 'a': 2}
Check 'a' → available → decrement count → {'b': 1, 'a': 1}
Check 'a' → available → decrement → {'b': 1, 'a': 0}
Check 'b' → available → decrement → {'b': 0, 'a': 0}
All characters found → return true

Time and Space Complexity

Time Complexity: O(M + R), where M is the length of magazine and R is the length of ransomNote.
Space Complexity: O(1), because the number of characters is limited (only lowercase English letters).

Edge Cases to Consider

Empty ransomNote → always return true
Empty magazine but non-empty ransomNote → always return false
Case sensitivity matters → "A" and "a" are different characters

Conclusion

The “Ransom Note” problem teaches how to efficiently manage and compare frequencies between two data sources. While the brute-force method demonstrates a naïve solution, the optimized version using a hash map offers a significant performance boost and is widely applicable to many real-world problems.

Get Personalized Support at AlgoMap Bootcamp 💡