🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires determining if we can construct the ransomNote
string using the letters available in the magazine
string. Each letter in the magazine
can only be used once. This means we need to ensure that for each character in ransomNote
, there is a corresponding character in magazine
that hasn't been used already.
Approach
- Count Characters in
magazine
: Use a dictionary to count the occurrences of each character inmagazine
. - Check Characters in
ransomNote
: Iterate through each character inransomNote
and check if it is present in the dictionary with a non-zero count. - If the character is present and its count is greater than zero, decrement the count. - If the character is not present or its count is zero, returnfalse
. - Return
true
: If all characters inransomNote
can be matched with characters inmagazine
, returntrue
.
This approach ensures that we efficiently check the availability of each character in ransomNote
against magazine
.
Complexity
Time Complexity
- Counting characters in
magazine
takesO(m)
time, wherem
is the length ofmagazine
. - Checking each character in
ransomNote
takesO(n)
time, wheren
is the length ofransomNote
. - Overall time complexity is
O(m + n)
.
Space Complexity
- The space complexity is
O(1)
since the dictionary will hold at most 26 key-value pairs if we consider only lowercase English letters. This can be considered constant space.
Code
C++
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
for (char c : magazine) {
size_t pos = ransomNote.find(c);
if (pos != string::npos) {
ransomNote.erase(pos, 1);
}
}
return ransomNote.empty();
}
};
Python
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
for char in magazine:
ransomNote = ransomNote.replace(char, '', 1)
return ransomNote == ''
Java
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
for (char c : magazine.toCharArray()) {
ransomNote = ransomNote.replaceFirst(String.valueOf(c), "");
}
return ransomNote.isEmpty();
}
}
JavaScript
var canConstruct = function (ransomNote, magazine)
{
for (const char of magazine)
{
ransomNote = ransomNote.replace(char, "");
}
if (!ransomNote) return true;
else return false;
};