Code Implementation

from collections import Counter

class Solution:
    def countCharacters(self, words, chars):
        chars_count = Counter(chars)
        total_length = 0
        
        for word in words:
            word_count = Counter(word)
            for c in word_count:
                if word_count[c] > chars_count.get(c, 0):
                    break
            else:
                total_length += len(word)
        return total_length
      

#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        vector<int> charsCount(26, 0);
        for (char c : chars) charsCount[c - 'a']++;
        int total = 0;
        for (const string& word : words) {
            vector<int> wordCount(26, 0);
            for (char c : word) wordCount[c - 'a']++;
            bool canForm = true;
            for (int i = 0; i < 26; ++i) {
                if (wordCount[i] > charsCount[i]) {
                    canForm = false;
                    break;
                }
            }
            if (canForm) total += word.size();
        }
        return total;
    }
};
      

import java.util.*;

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

var countCharacters = function(words, chars) {
    let charsCount = Array(26).fill(0);
    for (let c of chars) charsCount[c.charCodeAt(0) - 97]++;
    let total = 0;
    for (let word of words) {
        let wordCount = Array(26).fill(0);
        for (let c of word) wordCount[c.charCodeAt(0) - 97]++;
        let canForm = true;
        for (let i = 0; i < 26; i++) {
            if (wordCount[i] > charsCount[i]) {
                canForm = false;
                break;
            }
        }
        if (canForm) total += word.length;
    }
    return total;
};
      

Problem Description

You are given a list of strings called words and a string chars. Your task is to find out which words in words can be formed using the characters from chars, where each character in chars can only be used as many times as it appears in chars (no reusing or unlimited usage). For each word that can be formed, you sum up its length. Return the total length of all such words.

• You cannot reuse a character in chars more than its count.
• Each word must be formed using only the available characters.
• Words can be of different lengths and may require different letters.

Thought Process

At first glance, the problem seems to require checking each word and seeing if it can be constructed from chars. The naive way is to, for each word, try to match its letters with those in chars, removing used letters each time. However, this would be inefficient, especially with many words or long strings.

To optimize, we realize that the order of letters doesn't matter—only the count of each letter is important. So, if we count how many times each letter appears in chars and compare that with how many times a word needs each letter, we can quickly check if a word is buildable. This shifts our approach from string manipulation to using frequency counts or hash maps for fast lookup and comparison.

Solution Approach

• Step 1: Count Characters in chars
  • Use a hash map (or array for 26 letters) to count how many times each letter appears in chars.
• Step 2: For Each Word, Count Its Letters
  • For each word in words, count the frequency of each letter.
• Step 3: Compare Letter Counts
  • For every letter in the word, check if the required number is less than or equal to the number available in chars.
  • If any letter is needed more times than available, skip the word.
• Step 4: Sum Lengths of Valid Words
  • If a word can be formed, add its length to a running total.
• Step 5: Return the Total
  • Return the final sum after all words are checked.

We use arrays for counting when the alphabet is limited (like lowercase English letters), as lookups are O(1) and memory usage is minimal.

Example Walkthrough

Suppose words = ["cat", "bt", "hat", "tree"] and chars = "atach".

1. Count letters in chars: a:2, t:1, c:1, h:1.
2. For "cat": c:1, a:1, t:1. All counts are within what's available. Add 3 to total.
3. For "bt": b:1, t:1. "b" is not in chars. Skip.
4. For "hat": h:1, a:1, t:1. All counts are available. Add 3 to total (total is now 6).
5. For "tree": t:1, r:1, e:2. "r" and "e" are not in chars. Skip.
6. Return 6.

Only "cat" and "hat" can be formed, so their lengths (3+3) are summed.

Time and Space Complexity

• Brute-force: For each word, try to form it by removing letters from a copy of chars. This could be O(n * m^2), where n is the number of words and m is the average word length, due to repeated string operations.
• Optimized (Using Counts): Counting letters in chars is O(L), where L is the length of chars. For each word, counting is O(m), and comparison is O(1) (since the alphabet is fixed at 26). So, total time is O(L + n * m).
• Space: O(1) for the counts (since the alphabet is fixed), plus O(m) for each word's count (but not cumulative).

Summary

The key insight is to use frequency counts to quickly check if a word can be built from the available letters, avoiding inefficient string manipulations. By shifting to this counting strategy, we achieve a solution that is both simple and efficient. The elegance comes from leveraging the fixed size of the character set for constant-time checks, making the code readable and performant.