Ransom Note

Problem

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note: You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

Solution

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

Analysis

We can have many solutions to solve this problem
But their ideas are all similar, to record the frequency of char in one and compare it to another
We can have HashMap to do that, but since there are only lowercase letters, we use int[26] in this solution
We store each char from magazine with its frequency
Then we check each char in ransomNote and return false if there is any letter missing
At the end, we return true because all letters are there in magazine

Complexity

• Time: O(n), where n is the max length of magazine or ransomNote
• Space: O(1), only constant space is used