Description

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:

1Input: ransomNote = "a", magazine = "b"
2Output: false

Example 2:

1Input: ransomNote = "aa", magazine = "ab"
2Output: false

Example 3:

1Input: ransomNote = "aa", magazine = "aab"
2Output: true

Constraints:

  • 1 <= ransomNote.length, magazine.length <= 10^5
  • ransomNote and magazine consist of lowercase English letters.

Solution

This problem is again similar to calculating the number of times a given character in ransomNote occurs and check if we have all charactesr in magazine or if those are more than once, then check how many times they are in magazine.

Using Array

This can be solved using arrays. The problem states that all chracters are lowercase English characters. Therefore, we can store the occurrences for those characters in an array of size 26, where index 0 stores frequency of ‘a’ and so on. When we have a character appearing more than once, we have to validate that we have enough frequency for that character.

 1class Solution {
 2    public boolean canConstruct(String ransomNote, String magazine) {
 3        int[] charCounts = new int[26];
 4        for (char c: magazine.toCharArray()) {
 5            charCounts[c - 'a']++;
 6        }
 7        for (char c: ransomNote.toCharArray()) {
 8            charCounts[c - 'a']--;
 9            if (charCounts[c - 'a'] < 0) {
10                return false;
11            }
12        }
13        return true;
14    }
15}
  • Time Complexity: O(n)
  • Space Complexity: O(1) because, it can have upto 26 cells in an array.

Using HashMap

In this case, we store the frequency of characters in a Hash map.

 1class Solution {
 2    public boolean canConstruct (String ransomNote, String magazine) {
 3        Map<Character, Integer> charCounts = new HashMap<>();
 4        for (char c: magazine.toCharArray()) {
 5            charCounts.put(c, charCounts.getOrDefault(c, 0) + 1);
 6        }
 7        for (char c: ransomNote.toCharArray()) {
 8            charCounts.put(c, charCounts.getOrDefault(c, 0) - 1);
 9            if (charCounts.get(c) < 0) {
10                return false;
11            }
12        }
13        return true;
14    }
15}
  • Time Complexity: O(n)
  • Space Complexity: O(1) because at worst case, it can have at most 26 unique keys for each of the lowercase English characters.