Problem Description

You are given an array of strings called words and a string called chars.

A string from the words array is considered "good" if you can form it using only the characters available in chars. Each character in chars can only be used once per word (but the same chars string can be used to check multiple words).

Your task is to find all the "good" strings in the words array and return the sum of their lengths.

For example:

• If chars = "atach" and words = ["cat", "bt", "hat", "tree"]
• "cat" can be formed using 'c', 'a', 't' from chars → good string (length 3)
• "bt" cannot be formed because there's no 'b' in chars → not good
• "hat" can be formed using 'h', 'a', 't' from chars → good string (length 3)
• "tree" cannot be formed because chars only has one 't' but "tree" needs two → not good
• The answer would be 3 + 3 = 6

The key constraint is that each character in chars can only be used once when checking if a single word can be formed. You need to ensure that the frequency of each character in a word doesn't exceed the frequency of that character in chars.

Intuition

The core challenge here is determining whether we have enough characters in chars to build each word. This is fundamentally a frequency comparison problem.

Think of it like having a bag of letter tiles (like in Scrabble). The string chars represents all the tiles we have available. For each word, we need to check if we have enough of each required letter tile to spell that word.

The natural approach is to count how many of each character we have available in chars, and then for each word, count how many of each character we need. If for every character in the word, we have at least as many available in chars, then we can form that word.

For example, if chars = "aabbc", we have:

• 2 'a's
• 2 'b's
• 1 'c'

If we want to check the word "abc", we need 1 'a', 1 'b', and 1 'c'. Since we have enough of each, we can form it.

If we want to check the word "aaab", we need 3 'a's and 1 'b'. But we only have 2 'a's available, so we cannot form this word.

This leads us to use frequency counting (Counter in Python) - first count the available characters in chars, then for each word, count its character requirements and compare. If all character requirements are met, add that word's length to our answer.

Solution Approach

We implement the frequency counting approach using Python's Counter data structure.

Step 1: Count available characters

cnt = Counter(chars)

This creates a frequency map of all characters in chars. For example, if chars = "atach", then cnt would be {'a': 2, 't': 1, 'c': 1, 'h': 1}.

Step 2: Initialize the answer

ans = 0

This will store the sum of lengths of all good strings.

Step 3: Check each word

for w in words:
    wc = Counter(w)

For each word w in the words array, we create a frequency map wc of its characters.

Step 4: Verify if the word can be formed

if all(cnt[c] >= v for c, v in wc.items()):
    ans += len(w)

This is the key validation step. We iterate through each character c and its count v in the word's frequency map wc. For each character:

• cnt[c] gives us how many times character c appears in chars
• v tells us how many times we need character c for the current word
• We check if cnt[c] >= v (do we have enough of this character?)

The all() function returns True only if this condition holds for every character in the word. If it does, we can form the word, so we add its length to our answer.

Step 5: Return the result

return ans

The time complexity is O(N × M) where N is the number of words and M is the average length of each word, since we need to count characters for each word. The space complexity is O(1) as the Counter objects can have at most 26 entries (for lowercase English letters).

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• chars = "aabbc"
• words = ["ab", "abc", "baa", "cc"]

Step 1: Count available characters in chars

cnt = Counter("aabbc")
# cnt = {'a': 2, 'b': 2, 'c': 1}

We have 2 'a's, 2 'b's, and 1 'c' available.

Step 2: Initialize answer

ans = 0

Step 3: Check each word

Word 1: "ab"

wc = Counter("ab")  # wc = {'a': 1, 'b': 1}

Check if we can form it:

• Need 1 'a', have 2 'a's ✓ (2 >= 1)
• Need 1 'b', have 2 'b's ✓ (2 >= 1)
• All checks pass! Add length: ans = 0 + 2 = 2

Word 2: "abc"

wc = Counter("abc")  # wc = {'a': 1, 'b': 1, 'c': 1}

Check if we can form it:

• Need 1 'a', have 2 'a's ✓ (2 >= 1)
• Need 1 'b', have 2 'b's ✓ (2 >= 1)
• Need 1 'c', have 1 'c' ✓ (1 >= 1)
• All checks pass! Add length: ans = 2 + 3 = 5

Word 3: "baa"

wc = Counter("baa")  # wc = {'b': 1, 'a': 2}

Check if we can form it:

• Need 1 'b', have 2 'b's ✓ (2 >= 1)
• Need 2 'a's, have 2 'a's ✓ (2 >= 2)
• All checks pass! Add length: ans = 5 + 3 = 8

Word 4: "cc"

wc = Counter("cc")  # wc = {'c': 2}

Check if we can form it:

• Need 2 'c's, have 1 'c' ✗ (1 < 2)
• Check fails! Don't add this word's length.

Step 4: Return the result

return ans  # Returns 8

The final answer is 8, which is the sum of lengths of "ab" (2) + "abc" (3) + "baa" (3).

Solution Implementation

Time and Space Complexity

The time complexity is O(L), where L is the sum of the lengths of all strings in the problem (including the length of chars and the total length of all words in words). Breaking this down:

• Creating Counter(chars) takes O(n) where n is the length of chars
• For each word w in words, creating Counter(w) takes O(m) where m is the length of that word
• Checking all(cnt[c] >= v for c, v in wc.items()) iterates through at most m unique characters in word w
• The total operations across all words is proportional to the sum of all string lengths

The space complexity is O(C), where C is the size of the character set. In this problem, C = 26 (lowercase English letters). This is because:

• Counter(chars) stores at most C unique characters
• Each Counter(w) also stores at most C unique characters
• Since we only maintain one word counter at a time (not storing all of them), the space used is bounded by O(C)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Reusing Characters Across Multiple Checks

A common mistake is thinking that characters from chars get "consumed" when checking words. Each word is checked independently against the full chars string.

Incorrect thinking:

# WRONG: Modifying the character count
char_count = Counter(chars)
for word in words:
    word_char_count = Counter(word)
    if all(char_count[char] >= count for char, count in word_char_count.items()):
        total_length += len(word)
        # DON'T DO THIS - subtracting used characters
        for char, count in word_char_count.items():
            char_count[char] -= count

Correct approach: Each word gets checked against the original chars independently. The same char_count is reused for all words without modification.

Pitfall 2: Not Handling Missing Characters Properly

When a character in the word doesn't exist in chars, Counter returns 0 by default, which makes the comparison work correctly. However, using a regular dictionary would cause a KeyError.

Problematic code:

# Using regular dict instead of Counter
char_count = {}
for c in chars:
    char_count[c] = char_count.get(c, 0) + 1

for word in words:
    word_char_count = {}
    for c in word:
        word_char_count[c] = word_char_count.get(c, 0) + 1
  
    # This would fail if word contains a character not in chars
    if all(char_count[char] >= count for char, count in word_char_count.items()):
        # KeyError if char not in char_count

Solution: Either use Counter (which returns 0 for missing keys) or handle missing keys explicitly:

if all(char_count.get(char, 0) >= count for char, count in word_char_count.items()):

Pitfall 3: Character Frequency vs Character Presence

Simply checking if all characters exist in chars is insufficient. You must verify that the frequency requirements are met.

Wrong approach:

# INCORRECT: Only checks presence, not frequency
chars_set = set(chars)
for word in words:
    if all(c in chars_set for c in word):
        total_length += len(word)

This would incorrectly accept "tree" when chars = "ter" because all unique characters ('t', 'r', 'e') are present, ignoring that we need two 'e's.

Correct approach: Always compare character frequencies, not just presence.