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 <= 105ransomNote and magazine consist of lowercase English letters.Problem Overview: You are given two strings: ransomNote and magazine. Determine whether the ransom note can be constructed using letters from the magazine. Each character in magazine can only be used once, so you must verify that the magazine contains at least the same frequency of every character required by the ransom note.
Approach 1: Frequency Counting with Hash Maps (Time: O(n + m), Space: O(1))
This method counts how many times each character appears in the magazine, then checks whether the ransom note can consume those counts. First iterate through magazine and store frequencies in a hash map or fixed-size array for lowercase letters. Then iterate through ransomNote, decrementing the count for each character. If any count becomes negative or missing, the note cannot be constructed. The key insight: verifying character availability is a constant-time hash lookup instead of repeatedly scanning the string.
Because the alphabet is limited (26 lowercase letters), the auxiliary space is effectively constant. This approach runs in linear time relative to the combined lengths of both strings. It’s the most direct solution using hash tables and frequency counting, and it works well for any string size.
Approach 2: Sorting and Two Pointers (Time: O(n log n + m log m), Space: O(1) or O(n))
This strategy sorts both strings first. After sorting, traverse them using two pointers. One pointer scans the sorted magazine string while the other tracks characters in ransomNote. When characters match, advance both pointers since the letter is successfully used. If the magazine character is smaller, advance only the magazine pointer. If the ransom note character is smaller, construction is impossible because the required letter does not exist ahead.
The sorted ordering groups identical characters together, which makes comparison straightforward without a hash map. However, sorting introduces an O(n log n) cost, making it slower than the counting approach for large inputs. This method mainly demonstrates pointer techniques on sorted string data.
Recommended for interviews: Frequency counting with a hash map or fixed array is the expected answer. It runs in linear time and directly models the constraint that each magazine letter can only be used once. Interviewers often accept either a hash map or a 26-length integer array. Explaining the sorting approach shows awareness of alternative strategies, but the O(n) counting solution demonstrates stronger algorithmic judgment.
This approach involves using hash maps to count the frequency of each letter in both ransomNote and magazine. The idea is to determine if magazine has enough of each letter to build ransomNote.
magazine.ransomNote and check if the magazine frequency is sufficient.ransomNote has a higher frequency than in magazine, return false.true.The solution uses an array count of size 26 to store the frequency of each character from 'a' to 'z'. It first increments the counts based on the characters in magazine and then decrements the respective counts as it encounters each character in ransomNote. If any count goes negative, it indicates that ransomNote cannot be formed, hence returning false.
Time Complexity: O(m + n), where m and n are the lengths of magazine and ransomNote, respectively.
Space Complexity: O(1), as the space is allocated for a fixed-size frequency array.
Instead of counting character frequencies, we can sort both ransomNote and magazine and use a two-pointer technique to check if magazine contains all letters needed for ransomNote in a sorted order.
ransomNote and magazine.ransomNote are matched, return true; otherwise, return false.This C solution sorts both strings using qsort and iterates using two indices, attempting to match each character from ransomNote with a character from magazine.
Time Complexity: O(n log n + m log m), dominated by sorting
Space Complexity: O(1)
We can use a hash table or an array cnt of length 26 to record the number of times each character appears in the string magazine. Then traverse the string ransomNote, for each character c in it, we decrease the number of c by 1 in cnt. If the number of c is less than 0 after the decrease, it means that the number of c in magazine is not enough, so it cannot be composed of ransomNote, just return false.
Otherwise, after the traversal, it means that each character in ransomNote can be found in magazine. Therefore, return true.
The time complexity is O(m + n), and the space complexity is O(C). Where m and n are the lengths of the strings ransomNote and magazine respectively; and C is the size of the character set, which is 26 in this question.
| Approach | Complexity |
|---|---|
| Approach 1: Frequency Counting with Hash Maps | Time Complexity: O(m + n), where m and n are the lengths of |
| Approach 2: Sorting and Two Pointers | Time Complexity: O(n log n + m log m), dominated by sorting |
| Hash Table or Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Counting with Hash Map | O(n + m) | O(1) | General case. Fastest solution when checking character availability. |
| Sorting and Two Pointers | O(n log n + m log m) | O(1) or O(n) | Useful when data is already sorted or when practicing two-pointer techniques. |
Ransom note | Leetcode #383 • Techdose • 26,411 views views
Watch 9 more video solutions →Practice Ransom Note with our built-in code editor and test cases.
Practice on FleetCode