Ransom Note

easy string hash map

Problem

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false. Each letter in the magazine string can only be used once in your ransom note.

Inputnote = "aab", magazine = "baa"

Outputtrue

Two a's and one b are available; note needs exactly that.

note

magazine

from collections import Counter

def can_construct(note, magazine):
    counts = Counter(magazine)
    for c in note:
        if counts[c] == 0:
            return False
        counts[c] -= 1
    return True

function canConstruct(note, magazine) {
  const counts = new Map();
  for (const c of magazine) counts.set(c, (counts.get(c) || 0) + 1);
  for (const c of note) {
    const left = counts.get(c) || 0;
    if (left === 0) return false;
    counts.set(c, left - 1);
  }
  return true;
}

class Solution {
    public boolean canConstruct(String note, String magazine) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : magazine.toCharArray()) counts.merge(c, 1, Integer::sum);
        for (char c : note.toCharArray()) {
            int left = counts.getOrDefault(c, 0);
            if (left == 0) return false;
            counts.put(c, left - 1);
        }
        return true;
    }
}

bool canConstruct(string note, string magazine) {
    unordered_map<char, int> counts;
    for (char c : magazine) counts[c]++;
    for (char c : note) {
        if (counts[c] == 0) return false;
        counts[c]--;
    }
    return true;
}

Explanation

The note can be built only if the magazine has enough of every letter the note needs. So the natural plan is to count letters and check there are no shortages.

First we tally how many of each character the magazine has using a Counter (a letter-to-count map). This counts map is our pool of available letters.

Then we walk through the note one character at a time. For each character c, if counts[c] is already 0 we are short and immediately return False. Otherwise we "spend" one copy by doing counts[c] -= 1, since each magazine letter can be used only once.

If we get through the entire note without ever running out, every needed letter was available, so we return True.

Example: note = "aab", magazine = "baa". Counts start as {b:1, a:2}. We use a (now a:1), a again (a:0), then b (b:0) — never blocked, so the answer is True.

Time: O(n + m) Space: O(σ)