Find Words That Can Be Formed by Characters

easy hash map frequency count string

Problem

You are given an array of strings words and a string chars. A word is good if it can be formed using the letters of chars, where each letter can be used at most once. Return the sum of lengths of all good words.

Inputwords = ["cat", "bt", "hat", "tree"], chars = "atach"

Output6

"cat" (3) and "hat" (3) can be formed from "atach"; "bt" and "tree" cannot. 3 + 3 = 6.

words (comma-separated)

chars

def count_characters(words, chars):
    from collections import Counter
    avail = Counter(chars)
    total = 0
    for word in words:
        need = Counter(word)
        if all(need[c] <= avail[c] for c in need):
            total += len(word)
    return total

function countCharacters(words, chars) {
  const avail = {};
  for (const c of chars) avail[c] = (avail[c] || 0) + 1;
  let total = 0;
  for (const word of words) {
    const need = {};
    for (const c of word) need[c] = (need[c] || 0) + 1;
    let ok = true;
    for (const c in need) if (need[c] > (avail[c] || 0)) ok = false;
    if (ok) total += word.length;
  }
  return total;
}

class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] avail = new int[26];
        for (char c : chars.toCharArray()) avail[c - 'a']++;
        int total = 0;
        for (String word : words) {
            int[] need = new int[26];
            for (char c : word.toCharArray()) need[c - 'a']++;
            boolean ok = true;
            for (int i = 0; i < 26; i++) if (need[i] > avail[i]) ok = false;
            if (ok) total += word.length();
        }
        return total;
    }
}

int countCharacters(vector<string>& words, string chars) {
    int avail[26] = {0};
    for (char c : chars) avail[c - 'a']++;
    int total = 0;
    for (auto& word : words) {
        int need[26] = {0};
        for (char c : word) need[c - 'a']++;
        bool ok = true;
        for (int i = 0; i < 26; i++) if (need[i] > avail[i]) ok = false;
        if (ok) total += (int)word.size();
    }
    return total;
}

Explanation

A word is spellable from chars only if, for every letter, the word needs no more copies than chars actually has. So we compare letter frequencies, not just which letters appear.

First we count the letters of chars into a pool, avail. This is our budget: how many of each letter we can spend.

For each word we count its own letters into need, then check that need[c] <= avail[c] for every letter c the word uses. If even one letter falls short, the word is rejected; otherwise it is "good" and we add its length to the running total.

Example: chars = "atach" gives a pool of a:2, t:1, c:1, h:1. The word "cat" needs c:1, a:1, t:1, all within budget, so it counts (length 3). "hat" also fits (length 3). "bt" needs a b the pool lacks, and "tree" needs two es and an r it does not have. Total is 3 + 3 = 6.

Counting each word fresh against the same pool keeps the letters independent, so one word never "uses up" the budget for the next.

Time: O(n + Σ|word|) Space: O(1)