Ransom Note
EasyPrompt
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process of constructing the ransom note. For each character required by the ransom note, we search for it in the magazine. If found, we mark it as used to prevent it from being used again.
Algorithm
- Convert the
magazinestring to a mutable data structure like aStringBuilder. - Iterate through each character
cof theransomNote. - For each
c, search for its first occurrence in themagazinestructure. - If
cis found at indexi, remove it to mark it as used (e.g.,magazine.deleteCharAt(i)). - If
cis not found, it's impossible to form the note, so returnfalse. - If the loop completes successfully, it means all characters were found, so return
true.
Walkthrough
The algorithm iterates through every character of the ransomNote. For each character, it searches for a corresponding match in the magazine. To ensure that each letter from the magazine is used only once, we must 'consume' the character from the magazine once it's used. A simple way to do this is to convert the magazine string into a more flexible data structure like a StringBuilder. When a character is found, we can delete it from the structure. If at any point we cannot find a required character for the ransomNote, we know it's impossible to construct, and we return false. If we successfully find and consume a character from the magazine for every character in the ransomNote, we return true.
class Solution { public boolean canConstruct(String ransomNote, String magazine) { if (ransomNote.length() > magazine.length()) { return false; } StringBuilder magazineBuilder = new StringBuilder(magazine); for (char c : ransomNote.toCharArray()) { int index = magazineBuilder.indexOf(String.valueOf(c)); if (index == -1) { return false; } magazineBuilder.deleteCharAt(index); } return true; }}Complexity
Time
O(n * m), where n is the length of the `ransomNote` and m is the length of the `magazine`. For each of the n characters in the ransom note, we might have to scan the entire magazine of length m to find it.
Space
O(m), where m is the length of the magazine. This is because we need a mutable copy of the magazine string (e.g., a `StringBuilder`) to mark characters as used.
Trade-offs
Pros
Simple to conceptualize and implement.
Doesn't require any advanced data structures.
Cons
Highly inefficient, with a time complexity that is quadratic in the lengths of the strings.
Performs poorly on large inputs due to the nested search operation.
A more optimized approach involves sorting both the ransom note and the magazine. Once sorted, we can use a two-pointer technique to efficiently check if all characters of the ransom note can be found in the magazine in the correct quantities.
Algorithm
- Convert both
ransomNoteandmagazineto character arrays. - Sort both character arrays alphabetically.
- Initialize two pointers,
ifor theransomNotearray andjfor themagazinearray, both starting at 0. - While both pointers are within their respective array bounds:
- If
magazine[j] < ransomNote[i], we need a larger character from the magazine, so incrementj. - If
magazine[j] == ransomNote[i], we found a match. Increment bothiandj. - If
magazine[j] > ransomNote[i], it means the characterransomNote[i]is not available in the magazine, so returnfalse.
- If
- After the loop, if pointer
ihas traversed the entireransomNotearray, it means all characters were found. Returntrue.
Walkthrough
This method leverages the power of sorting to simplify the comparison. By sorting both the ransomNote and magazine strings alphabetically, we can check for the availability of characters in a single pass using two pointers. We maintain one pointer for the ransomNote and one for the magazine. We advance the pointers based on character comparison. If the magazine character is smaller than the ransomNote character, we move to the next character in the magazine to find a potential match. If they are equal, we've found a match for the current ransomNote character, so we advance both pointers. If the magazine character is larger, it means we've skipped past the required character in the sorted magazine, so a match is impossible.
import java.util.Arrays; class Solution { public boolean canConstruct(String ransomNote, String magazine) { if (ransomNote.length() > magazine.length()) { return false; } char[] noteChars = ransomNote.toCharArray(); char[] magChars = magazine.toCharArray(); Arrays.sort(noteChars); Arrays.sort(magChars); int notePtr = 0; int magPtr = 0; while (notePtr < noteChars.length && magPtr < magChars.length) { if (magChars[magPtr] < noteChars[notePtr]) { magPtr++; } else if (magChars[magPtr] == noteChars[notePtr]) { notePtr++; magPtr++; } else { // magChars[magPtr] > noteChars[notePtr] return false; } } return notePtr == noteChars.length; }}Complexity
Time
O(m log m + n log n), where n and m are the lengths of the `ransomNote` and `magazine` respectively. The dominant operation is sorting the two strings. The subsequent two-pointer scan takes O(n + m) time.
Space
O(n + m) in Java. Strings are immutable, so `toCharArray()` creates copies of size n and m. The space used by the sorting algorithm itself is typically O(log n) or O(log m) for primitive types.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Logically straightforward after the sorting step.
Cons
The time complexity is dominated by sorting, which is not as fast as the linear-time hash map approach.
Requires extra space to hold the character arrays for sorting.
The most efficient approach uses a frequency counter to solve the problem in linear time. The idea is to count the occurrences of each character in the magazine. Then, we iterate through the ransom note and check if each required character is available in sufficient quantity.
Algorithm
- Create a frequency counter, such as an integer array of size 26 for lowercase English letters, initialized to zeros.
- Iterate through the
magazinestring. For each character, increment its corresponding count in the frequency array. - Iterate through the
ransomNotestring. - For each character
cin theransomNote:- Check the count for
cin the frequency array. If it's 0, the character is not available. Returnfalse. - If the count is greater than 0, decrement it to 'use up' the character.
- Check the count for
- If the loop over
ransomNotecompletes, it means all characters were available in sufficient quantities. Returntrue.
Walkthrough
This is the most optimal approach. The problem is fundamentally about character frequencies: for every character c, its frequency in ransomNote must be less than or equal to its frequency in magazine. We can efficiently track these frequencies using a hash map or, even better, a simple array if the character set is limited (e.g., 26 lowercase English letters).
First, we iterate through the magazine string and populate our frequency counter. Then, we iterate through the ransomNote. For each character in the note, we decrement its count in our frequency array. If we ever try to decrement a count that is already zero, it means the magazine did not have enough of that character, so we can immediately return false. If we successfully process all characters in the ransomNote, it means it can be constructed, and we return true.
class Solution { public boolean canConstruct(String ransomNote, String magazine) { if (ransomNote.length() > magazine.length()) { return false; } int[] counts = new int[26]; // For lowercase English letters // Count characters in magazine for (char c : magazine.toCharArray()) { counts[c - 'a']++; } // Check if ransomNote can be constructed for (char c : ransomNote.toCharArray()) { if (counts[c - 'a'] == 0) { return false; // Not enough characters } counts[c - 'a']--; } return true; }}Complexity
Time
O(n + m), where n is the length of the `ransomNote` and m is the length of the `magazine`. We perform a single pass over the magazine to build the frequency map and a single pass over the ransom note to check for characters.
Space
O(k), where k is the number of possible characters in the character set (the alphabet size). If the problem is constrained to lowercase English letters, k=26, making the space complexity constant, O(1).
Trade-offs
Pros
Optimal time complexity (linear).
Very efficient for large inputs.
Constant space complexity if the character set is fixed.
Cons
Requires extra space for the frequency map, although it's typically small and constant for a fixed alphabet.
Solutions
Solution
public class Solution { public bool CanConstruct ( string ransomNote , string magazine ) { int [] cnt = new int [ 26 ]; foreach ( var c in magazine ) { ++ cnt [ c - 'a' ]; } foreach ( var c in ransomNote ) { if (-- cnt [ c - 'a' ] < 0 ) { return false ; } } return true ; } }class Solution {public boolean canConstruct(String ransomNote, String magazine) { int[] cnt = new int[26]; for (int i = 0; i < magazine.length(); ++i) { ++cnt[magazine.charAt(i) - 'a']; } for (int i = 0; i < ransomNote.length(); ++i) { if (--cnt[ransomNote.charAt(i) - 'a'] < 0) { return false; } } return true; }}class Solution {public: bool canConstruct(string ransomNote, string magazine) { int cnt[26]{}; for (char &c : magazine) { ++cnt[c - 'a']; } for (char &c : ransomNote) { if (--cnt[c - 'a'] < 0) { return false; } } return true; }};class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: cnt = Counter(magazine) for c in ransomNote: cnt[c] -= 1 if cnt[c] < 0: return False return TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.