Find Words That Can Be Formed by Characters — Easy Problem & Solution

Problem statement

A word can be formed from chars if every letter it uses is available in chars at least as many times. Each letter of chars may be used at most once per word, but chars is not consumed between words.

Return the sum of the lengths of all words that can be formed.

Example 1

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: "cat" and "hat" can be formed: 3 + 3 = 6.

Example 2

Input: words = ["code","kairo","coco"], chars = "codekairo"
Output: 9
Explanation: "code" and "kairo" fit; "coco" needs two c's and only one is available.

Example 3

Input: words = ["a"], chars = "b"
Output: 0

Constraints

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• All strings consist of lowercase English letters.

How to solve Find Words That Can Be Formed by Characters

The budget is fixed, so tally chars once and then test each word against it with a 26-slot comparison.

Approach

1. Build have[26] from chars.
2. For each word, build need[26] and check need[c] <= have[c] for every letter.
3. Add the word's length when every slot passes.

Why it works

Because chars is not consumed between words, each word is an independent test against the same budget — so recomputing have per word would be wasted work, and a shared mutable budget would be wrong.

Complexity

• Time — O(total characters)
• Space — O(1)

Pitfalls

• Decrementing have as words are matched treats chars as consumable, which the statement does not.
• A set-based check ignores multiplicity and accepts "cook" from "cok".

Reference solution

Python

from typing import List

def countCharacters(words: List[str], chars: str) -> int:
    have = [0] * 26
    for c in chars:
        have[ord(c) - 97] += 1
    total = 0
    for w in words:
        need = [0] * 26
        for c in w:
            need[ord(c) - 97] += 1
        if all(need[i] <= have[i] for i in range(26)):
            total += len(w)
    return total

JavaScript

var countCharacters = function(words, chars) {
    var have = [];
    for (var t = 0; t < 26; t++) have.push(0);
    for (var i = 0; i < chars.length; i++) have[chars.charCodeAt(i) - 97]++;
    var total = 0;
    for (var j = 0; j < words.length; j++) {
        var w = words[j];
        var need = [];
        for (var u = 0; u < 26; u++) need.push(0);
        for (var k = 0; k < w.length; k++) need[w.charCodeAt(k) - 97]++;
        var ok = true;
        for (var c = 0; c < 26; c++) {
            if (need[c] > have[c]) { ok = false; break; }
        }
        if (ok) total += w.length;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Most Frequent Even Element Easy
• Rearrange Characters to Make Target String Easy
• Decode the Message Easy
• Existence of a Substring in a String and Its Reverse Easy