# Java O(n) Easy To Understand, Optimal Solution

• Explanation
The idea to this problem is to first record the frequency of each distinct character in magazine in a dictionary, charMap.

Then, we scan through ransomNote, while decrementing character counts in charMap. If the count for any character is null or equal to 0, then that tells us there is not enough of that particular character in magazine, so we return false.

If we scan through the entirety of ransomNote, then that means we had enough characters in magazine, so we return true.

Time Complexity
The time complexity is O(n) where n is the number of characters in input magazine, since we scan through all characters in magazine when constructing charMap and we scan through at most n characters in ransomNote (more than n characters means magazine obviously does not contain enough characters).

``````class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
// Quick check to see if ransomNote is impossible to be constructed
if (ransomNote.length() > magazine.length()) {
return false;
}

// Maps character to its frequency
Map<Character, Integer> charMap = new HashMap<>();

// Record the characters counts in magazine
for (int i = 0; i < magazine.length(); i++) {
char c = magazine.charAt(i);
Integer count = charMap.get(c);

if (count == null) {
charMap.put(c, 1);
} else {
charMap.put(c, count + 1);
}
}
// Decrement the character counts in ransomNote from charMap
for (int i = 0; i < ransomNote.length(); i++) {
char c = ransomNote.charAt(i);
Integer count = charMap.get(c);

// If magazine does not contain char c or not enough of it,
//    return false
if (count == null || count <= 0) {
return false;
}
// Otherwise, we decrement the count for char c
else {
charMap.put(c, count - 1);
}
}
return true;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.