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.
1var canConstruct = function(ransomNote, magazine) {
2 let count = {};
3 for (let char ofThe solution uses a JavaScript object to count the frequency of each character in magazine. It checks if the object has enough of every character to construct ransomNote.
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)
public class Solution {
public bool CanConstruct(string ransomNote, string magazine) {
char[] ransomArray = ransomNote.ToCharArray();
char[] magArray = magazine.ToCharArray();
Array.Sort(ransomArray);
Array.Sort(magArray);
int i = 0, j = 0;
while (i < ransomArray.Length && j < magArray.Length) {
if (ransomArray[i] == magArray[j]) {
i++;
}
j++;
}
return i == ransomArray.Length;
}
}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 C# solution involves sorting both character arrays of the input strings. It iteratively checks for every character in ransomNote if there is a corresponding character in magazine.