# Find Words That Can Be Formed by Characters
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-words-that-can-be-formed-by-characters)
Canonical: https://scaleengineer.com/dsa/problems/find-words-that-can-be-formed-by-characters
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table, String
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Karat](https://scaleengineer.com/companies/karat), [Datadog](https://scaleengineer.com/companies/datadog)
---
## Problem
You are given an array of strings `words` and a string `chars`.

A string is **good** if it can be formed by characters from `chars` (each character can only be used once for **each** word in `words`).

Return _the sum of lengths of all good strings in words_.

**Example 1:**

**Input:** words = ["cat","bt","hat","tree"], chars = "atach"
**Output:** 6
**Explanation:** The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

**Example 2:**

**Input:** words = ["hello","world","leetcode"], chars = "welldonehoneyr"
**Output:** 10
**Explanation:** The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

**Constraints:**

* `1 <= words.length <= 1000`
* `1 <= words[i].length, chars.length <= 100`
* `words[i]` and `chars` consist of lowercase English letters.

# Approaches
## Brute-Force with Character List
This approach iterates through each word and, for each word, checks if it can be formed from the characters in `chars`. It does this by creating a temporary list of characters from the `chars` string for each word. Then, for every character in the word, it tries to find and remove it from this temporary list. If any character from the word cannot be found in the list, the word is not "good". If all characters are found, the word is "good", and its length is added to the total.
**Time:** O(N * M * C), where `N` is the number of words, `M` is the average length of a word, and `C` is the length of `chars`. For each of the `N` words, we iterate through its `M` characters. For each character, `list.remove()` takes `O(C)` time. This leads to a high time complexity. · **Space:** O(C), where `C` is the length of the `chars` string. A new list of characters of size `C` is created for each word in the `words` array.
**Pros:** Simple to conceptualize and implement without advanced data structures.; Follows the problem description literally, making it easy to reason about.
**Cons:** Highly inefficient, especially for long `chars` strings and many words.; Repeatedly creating and scanning the character list is very slow.; The `contains` and `remove` operations on an `ArrayList` are linear in time, leading to poor overall performance.
### Explanation
The algorithm starts by initializing a sum variable to zero. It then enters a loop that processes each `word` from the input `words` array. Inside this loop, a mutable copy of the `chars` string is created, typically as a `List<Character>`. This is necessary because we need to "use up" characters for each word independently. A boolean flag, say `isGood`, is set to `true`. A nested loop iterates through each character of the current `word`. In this inner loop, we check if the character exists in our list copy of `chars`. If it exists, we remove one instance of that character from the list to simulate its usage. If it does not exist, the word cannot be formed. We set `isGood` to `false` and immediately break out of the inner loop, as there's no need to check further for this word. After the inner loop finishes, we check the `isGood` flag. If it's still `true`, it means all characters of the word were found in `chars`, so we add the length of the word to our running sum. Finally, after checking all words, the total sum is returned.

```java
import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int countCharacters(String[] words, String chars) {
        int goodWordsLengthSum = 0;
        for (String word : words) {
            List<Character> charList = new ArrayList<>();
            for (char c : chars.toCharArray()) {
                charList.add(c);
            }
            
            boolean isGood = true;
            for (char wordChar : word.toCharArray()) {
                // In Java, list.remove(Object) is needed to remove the element, not by index.
                if (charList.remove(Character.valueOf(wordChar))) {
                    // Character was found and removed.
                } else {
                    // Character was not found.
                    isGood = false;
                    break;
                }
            }
            
            if (isGood) {
                goodWordsLengthSum += word.length();
            }
        }
        return goodWordsLengthSum;
    }
}
```
### Algorithm
*   Initialize `sum = 0`.
*   For each `word` in `words`:
    *   Create a `List<Character>` from the `chars` string.
    *   Initialize a boolean `canForm = true`.
    *   For each character `c` in `word`:
        *   If `c` is present in the list, remove one occurrence of `c`.
        *   Else, set `canForm = false` and break the inner loop.
    *   If `canForm` is `true`, add `word.length()` to `sum`.
*   Return `sum`.

## Optimized Frequency Counting with Arrays
This is a highly efficient approach that uses frequency arrays to solve the problem in linear time. First, we count the frequency of each character in the `chars` string and store it in an array of size 26. Then, for each word, we also count its character frequencies and check if it can be formed by comparing its frequency map against the available characters' frequency map. A word is "good" if the count of each character it requires is less than or equal to the count of that character available in `chars`.
**Time:** O(C + S), where `C` is the length of `chars` and `S` is the sum of lengths of all words in `words`. Building `charsFreq` takes `O(C)`. Then, processing all words involves iterating through each character once to build frequency maps, which takes `O(S)` in total. The final comparison for each word takes O(26), which is constant time. This results in an overall linear time complexity relative to the total input size. · **Space:** O(1). We use a few fixed-size arrays of size 26. Since the alphabet size is constant, the space required does not scale with the input size.
**Pros:** Extremely efficient with linear time complexity.; Optimal solution for the given constraints.; Uses a simple and fast data structure (array) for frequency counting.
**Cons:** Slightly more complex to write than the naive approach.; The constant space usage is specific to a small, fixed character set (like lowercase English letters). It would be less efficient for a very large character set where a HashMap would be needed instead of an array.
### Explanation
The core idea is to move from character-by-character searching to a frequency-based comparison. Since the input consists of only lowercase English letters, an integer array of size 26 is a perfect and efficient tool for a frequency map.

First, we create an integer array, `charsFreq`, of size 26. We iterate through the `chars` string once and populate this array. For each character `c`, we increment the count at index `c - 'a'`. This gives us a complete count of available characters in `O(C)` time, where `C` is the length of `chars`.

Next, we initialize a `totalLength` sum to 0 and iterate through each `word` in the `words` array. For each `word`, we build its own frequency map, `wordFreq`, in the same way. After building the `wordFreq` map, we compare it against the `charsFreq` map. We loop from 0 to 25 (representing 'a' to 'z') and check if `wordFreq[i]` is greater than `charsFreq[i]` for any `i`. If it is, the word requires more of a certain character than available, so it's not a "good" word. If we complete the comparison loop without finding such a case, the word is "good", and we add its length to our `totalLength` sum. This process avoids any expensive string or list operations within the main loop, making it very fast.

```java
public class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] charsFreq = new int[26];
        for (char c : chars.toCharArray()) {
            charsFreq[c - 'a']++;
        }
        
        int goodWordsLengthSum = 0;
        for (String word : words) {
            int[] wordFreq = new int[26];
            for (char c : word.toCharArray()) {
                wordFreq[c - 'a']++;
            }
            
            boolean isGood = true;
            for (int i = 0; i < 26; i++) {
                if (wordFreq[i] > charsFreq[i]) {
                    isGood = false;
                    break;
                }
            }
            
            if (isGood) {
                goodWordsLengthSum += word.length();
            }
        }
        
        return goodWordsLengthSum;
    }
}
```
### Algorithm
*   Create an integer array `charsFreq` of size 26, initialized to zeros.
*   Iterate through each character `c` in `chars` and increment `charsFreq[c - 'a']`.
*   Initialize `sum = 0`.
*   For each `word` in `words`:
    *   Create a temporary integer array `wordFreq` of size 26.
    *   Iterate through each character `c` in `word` and increment `wordFreq[c - 'a']`.
    *   Initialize a boolean `canForm = true`.
    *   Iterate from `i = 0` to `25`. If `wordFreq[i] > charsFreq[i]`, set `canForm = false` and break.
    *   If `canForm` is `true`, add `word.length()` to `sum`.
*   Return `sum`.

# Solutions
### Java

```java
class Solution { public int countCharacters ( String [] words , String chars ) { int [] cnt = new int [ 26 ]; for ( int i = 0 ; i < chars . length (); ++ i ) { ++ cnt [ chars . charAt ( i ) - 'a' ]; } int ans = 0 ; for ( String w : words ) { int [] wc = new int [ 26 ]; boolean ok = true ; for ( int i = 0 ; i < w . length (); ++ i ) { int j = w . charAt ( i ) - 'a' ; if (++ wc [ j ] > cnt [ j ]) { ok = false ; break ; } } if ( ok ) { ans += w . length (); } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int countCharacters ( vector < string >& words , string chars ) { int cnt [ 26 ]{}; for ( char & c : chars ) { ++ cnt [ c - 'a' ]; } int ans = 0 ; for ( auto & w : words ) { int wc [ 26 ]{}; bool ok = true ; for ( auto & c : w ) { int i = c - 'a' ; if ( ++ wc [ i ] > cnt [ i ]) { ok = false ; break ; } } if ( ok ) { ans += w . size (); } } return ans ; } };
```

### Python

```python
class Solution : def countCharacters ( self , words : List [ str ], chars : str ) -> int : cnt = Counter ( chars ) ans = 0 for w in words : wc = Counter ( w ) if all ( cnt [ c ] >= v for c , v in wc . items ()): ans += len ( w ) return ans
```