Ransom Note

Ransom Note

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.

Examples

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false
Explanation: The magazine does not contain the letter 'a'.

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false
Explanation: The magazine only contains one 'a', but the ransom note needs two.

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true
Explanation: The magazine has two 'a's, which is enough for the ransom note.

Constraints

• 1 <= ransomNote.length, magazine.length <= 10^5
• ransomNote and magazine consist of lowercase English letters.

Expected Complexity

• Time: O(n + m) where n and m are the lengths of the ransom note and magazine
• Space: O(1). at most 26 keys in the frequency map