Construct a Ransom Note From a Magazine

easy string hash map

Problem

Given strings note and magazine, return whether note can be assembled by cutting out characters of magazine. Each magazine character can be used at most once. Count the characters in magazine with a hash map, then walk note: each character must have a positive remaining count, which we decrement as we consume it.

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;
}

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