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.The key idea in #383 Ransom Note is to check whether the characters required for the ransom note are available in the magazine text with sufficient frequency. Since each character in the magazine can only be used once, we must track how many times each letter appears.
A common and efficient strategy is to use a hash table (or frequency counter) to count characters from the magazine. First, iterate through the magazine string and store the count of each character. Then traverse the ransom note and reduce the corresponding count for each character. If a required character is missing or its count becomes negative, constructing the note is impossible.
Because the problem deals with lowercase English letters, you can also optimize by using a fixed-size array of length 26 instead of a hash map. This keeps the implementation simple and efficient while maintaining linear performance.
This counting approach ensures we only scan the strings once, resulting in efficient time and space usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Table Character Counting | O(n + m) | O(k) |
| Fixed Array (26 Letters) | O(n + m) | O(1) |
Techdose
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.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.
1#include <stdbool.h>
2#include <string.h>
3
4bool canConstruct(char * ransomNote, char * magazine) {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.
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.Time Complexity: O(n log n + m log m), dominated by sorting
Space Complexity: O(1)
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, the Ransom Note problem is a popular beginner-level interview question. It tests understanding of hash tables, frequency counting, and efficient string processing, which are common concepts in coding interviews.
The optimal approach uses a character frequency counter. Count how many times each letter appears in the magazine and then decrement counts while checking the ransom note. If any character is unavailable or insufficient, the note cannot be formed.
Character counting ensures that each letter from the magazine is used only as many times as it appears. This prevents reusing characters beyond their available frequency and allows quick validation of whether the ransom note can be constructed.
A hash table or frequency map is commonly used to track character counts. Since the problem typically involves lowercase English letters, a fixed array of size 26 is often even more efficient and simpler to implement.
This Java solution uses arrays to hold character data for sorting. The two-pointer approach checks characters in sorted order, allowing us to confirm if ransomNote can be derived from magazine.