Find Words That Can Be Formed by Characters — Editorial

Opening the reading…

Intuitionwhy frequency comparison captures the whole condition

A word can be formed exactly when chars contains enough copies of every letter in that word. The order does not matter: using one copy of a means only the number of remaining copies matters, not where that a appeared in chars.

Count each lowercase letter in chars. Then inspect each word independently, consuming one count whenever its letter appears. If any count would become negative, the word needs more copies of that letter than chars provides, so the word is not good. A successful word contributes its full length to the answer.

Approachone reusable inventory and one temporary inventory per word

Build an array of 26 counts from chars, because lowercase English letters can be represented directly by indices from 0 to 25.

Set the answer to zero and process each word independently, because characters consumed while checking one word must remain available for every other word.

Copy the counts from chars into a temporary array for the current word, so testing this word cannot reduce the inventory used by a later word.

For every character in the word, decrement its temporary count. If the result is negative, mark the word invalid and stop, because this word requires one more copy than chars contains.

If the word never makes a temporary count negative, add its length to the answer; otherwise add nothing because one missing character makes the entire word unusable.

Return the accumulated answer after all words have been checked, since the required result is the sum of lengths rather than the number of good words.

Complexitylinear in the characters that are actually inspected

MEASURE	BOUND	WHY
Time	O(m + S)	Building the source inventory reads each character of chars once. Across all words, each character is decremented at most once before a failing word stops early, so the total inspected input is no more than m + S.
Space	O(1) extra	The source and temporary arrays each contain 26 integers, a fixed alphabet-sized amount of working memory. The returned integer is not output storage, and there is no degradation for any input shape because the alphabet size stays fixed.

Here m is the length of chars and S is the sum of the lengths of all words. The alphabet has fixed size 26.

Annotated solutionC++ · frequency arrays · the version to write from memory

CPPCount chars once, consume a copied inventory for each word, and add successful word lengths.

#include <cstring>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        int cnt[26] = {0};
        for (char c : chars) {
            cnt[c - 'a']++;
        }

        int ans = 0;
        for (string& w : words) {
            int tmp[26];
            memcpy(tmp, cnt, sizeof(tmp));

            bool ok = true;
            for (char c : w) {
                if (--tmp[c - 'a'] < 0) {
                    ok = false;
                    break;
                }
            }

            if (ok) {
                ans += static_cast<int>(w.size());
            }
        }

        return ans;
    }
};

The decrement and check belong together. For a character c, decreasing tmp[c - 'a'] records that one copy has been used, while checking for a negative result detects the first shortage immediately. Breaking at that point is safe because the word is already impossible; the remaining letters cannot make it valid again.