Ransom Note easy

Problem Statement

Given two strings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

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

Steps

1. Create a character frequency map for the magazine string: We'll use a JavaScript object (or Map in other languages) to store the count of each character in the magazine.

2. Iterate through the ransomNote string: For each character in ransomNote, check if it exists as a key in the frequency map.

3. Check frequency: If the character exists, check if its count is greater than 0. If it is, decrement the count. If the character doesn't exist or its count is 0, it means we can't construct the ransomNote and we return false.

4. Return true: If we successfully iterate through the entire ransomNote without finding any missing or insufficient characters, it means we can construct the ransomNote from magazine, so we return true.

Explanation

The core idea is to efficiently check if the ransomNote can be formed using the characters available in the magazine. Using a frequency map allows for constant-time (O(1)) lookups and updates of character counts, which optimizes the overall time complexity.

Code (TypeScript)

function canConstruct(ransomNote: string, magazine: string): boolean {
    const magazineCharCount: { [key: string]: number } = {};

    // Create frequency map for magazine
    for (const char of magazine) {
        magazineCharCount[char] = (magazineCharCount[char] || 0) + 1;
    }

    // Check if ransomNote can be constructed
    for (const char of ransomNote) {
        if (!magazineCharCount[char] || magazineCharCount[char] === 0) {
            return false; // Character not found or count is zero
        }
        magazineCharCount[char]--;
    }

    return true; // Ransom note can be constructed
}


// Example usage
console.log(canConstruct("a", "b")); // false
console.log(canConstruct("aa", "aab")); // true
console.log(canConstruct("aa", "ab")); // false

Complexity

• Time Complexity: O(m + n), where m is the length of ransomNote and n is the length of magazine. We iterate through both strings once.
• Space Complexity: O(k), where k is the number of unique characters in magazine. The space used is proportional to the size of the frequency map. In the worst case, k could be equal to n (length of magazine), but often it will be smaller.