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 <= 105
- ransomNote and magazine consist of lowercase English letters.
My Solution
We can iterate through both ransomNote and magazine and find the counts of each character. Then we can traverse the counts of magazine and if there is any character that occurs more times in ransomNote than magazine, we return false. Otherwise we return true.
Time complexity is O(m+n) to generate counts for both ransomNote and magazine, where m is the length of ransomNote and n is the length of magazine. Space complexity is O(1) since our counts arrays both have constant length of 26.
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] ransomeCounts = new int[26];
int[] magCounts = new int[26];
int m = ransomNote.length();
int n = magazine.length();
for (int i = 0; i < m; i++) {
ransomeCounts[ransomNote.charAt(i) - 'a']++;
}
for (int i = 0; i < n; i++) {
magCounts[magazine.charAt(i) - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (magCounts[i] < ransomeCounts[i]) {
return false;
}
}
return true;
}
}