Ransom Note

Problem Statement

LeetCode-383: 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.

Approach

The constraint that each letter in magazine is lowercase English letters allows us to use a frequency array to solve the problem.

We can keep track of the frequency of each character in the magazine string. Then, we can iterate over the ransomNote string and decrement the frequency of each character in the frequency array.

If the frequency of any character becomes negative or zero, we can return false.

Implementation

Following is the implementation of the above approach.

public boolean canConstruct(String ransomNote, String magazine) {
    char[] freq = new char[26];
    for(char ch : magazine.toCharArray()){
        freq[ch-'a']++;
    }
    for(char ch : ransomNote.toCharArray()){
        if(freq[ch-'a'] <= 0){
            return false;
        }else{
            freq[ch-'a']--;
        }
    }
    return true;
}

Complexity Analysis

The time complexity for this approach is \(O(n)\), where n is the length of the ransomNote string. The space complexity is \(O(1)\) since the frequency array has a fixed size of 26.