Ransom Note
Problem Description
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.
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
Constraints:
- 1 <= ransomNote.length, magazine.length <= 105
ransomNoteandmagazineconsist of lowercase English letters.
Solve it on LeetCode
Approaches
1. Frequency Counting Using Arrays
Intuition:
The problem is asking whether we can construct the ransomNote string using the characters from the magazine string. We can think of this as checking if there are enough characters available in magazine to cover each character requirement in ransomNote.
The basic idea is to count the frequency of each character in both ransomNote and magazine. Then, check if for every character in ransomNote, the count of that character in magazine is greater than or equal to its count in ransomNote.
Code:
We can use an integer array of size 26 to count the frequency of characters since the problem guarantees lowercase English letters only.
- Time Complexity: O(m + n), where
mis the length of themagazineandnis the length ofransomNote, since we iterate over both strings once. - Space Complexity: O(1), since the space used is constant (26), regardless of the input size.
2. Frequency Counting Using HashMap
Intuition:
Similar to the array-based approach, but using a HashMap allows the solution to easily be extended to encompass a broader set of characters if constraints were to change.
Code:
We will use a HashMap to store frequencies of characters in magazine and then check each character in ransomNote against this frequency map.
- Time Complexity: O(m + n), where
mis the length of themagazineandnis the length ofransomNote, since we iterate over both strings once. - Space Complexity: O(1) theoretically because the map keys are bounded by a fixed range (26 lowercase letters), though practically hash maps might grow depending on collisions and load.