Ransome Note

---

Ransome Note: 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 <= 10^5
• ransomNote and magazine consist of lowercase English letters.

---

Try this Problem on your own or check similar problems:

1. Stickers to Spell Word

Solution:

Java

public boolean canConstruct(String ransomNote, String magazine) {
    if(ransomNote.length() > magazine.length()) return false;
    int[] freq = new int[26];
    for(int i = 0; i < magazine.length(); ++i){
        ++freq[magazine.charAt(i) - 'a'];
    }

    for(int i = 0; i < ransomNote.length(); ++i){
        if(--freq[ransomNote.charAt(i) - 'a'] < 0) return false;
    }

    return true;
}

JavaScript

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function (ransomNote, magazine) {
  if (ransomNote.length > magazine.length) return false;
  let freq = new Array(26).fill(0);

  for (let i = 0; i < magazine.length; ++i) {
    ++freq[magazine.charCodeAt(i) - 97];
  }

  for (let i = 0; i < ransomNote.length; ++i) {
    if (--freq[ransomNote.charCodeAt(i) - 97] < 0) return false;
  }

  return true;
};

Python

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(ransomNote) > len(magazine):
            return False
        freq = [0] * 26

        for i in range(len(magazine)):
            freq[ord(magazine[i]) - 97] += 1

        for i in range(len(ransomNote)):
            if freq[ord(ransomNote[i]) - 97] - 1 < 0:
                return False
            freq[ord(ransomNote[i]) - 97] -= 1

        return True

C++

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if (ransomNote.length() > magazine.length()) return false;
        vector<int> freq(26, 0);

        for (int i = 0; i < magazine.length(); ++i) {
            ++freq[magazine[i] - 'a'];
        }

        for (int i = 0; i < ransomNote.length(); ++i) {
            if (--freq[ransomNote[i] - 'a'] < 0) return false;
        }

        return true;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(m) where m is the length of input string given as magazine
• Space Complexity: O(1)

---

Explanation:

We have a linear time complexity where n is the length of magazine and we utilize almost the same approach as we did in Valid Anagram. We're incrementing the freq for each letter in magazine and the decrementing it for ransomNote while also checking if the current count is smaller than 0 (we don't have enough letters). Finally if don't break early from the for loop in case we don't have enough of required letters we return true as our final result since we can create ransom from the magazine.