<p>You are given an array of strings <code>words</code> and a string <code>chars</code>.</p>

<p>A string is <strong>good</strong> if it can be formed by characters from <code>chars</code> (each character can only be used once).</p>

<p>Return <em>the sum of lengths of all good strings in words</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;cat&quot;,&quot;bt&quot;,&quot;hat&quot;,&quot;tree&quot;], chars = &quot;atach&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> The strings that can be formed are &quot;cat&quot; and &quot;hat&quot; so the answer is 3 + 3 = 6.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;hello&quot;,&quot;world&quot;,&quot;leetcode&quot;], chars = &quot;welldonehoneyr&quot;
<strong>Output:</strong> 10
<strong>Explanation:</strong> The strings that can be formed are &quot;hello&quot; and &quot;world&quot; so the answer is 5 + 5 = 10.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 1000</code></li>
	<li><code>1 &lt;= words[i].length, chars.length &lt;= 100</code></li>
	<li><code>words[i]</code> and <code>chars</code> consist of lowercase English letters.</li>
</ul>

'''
Approach 1: Brute Force
1) iterate through each word in 'words'
2) for each word, check if it can be formed using the characters in 'chars'
3) If yes, add length of word to the result

Time: O(n * m * k), Space: O(1)
n - number of words
m - average length of a word
k - length of chars
 '''

# class Solution:
#     def countCharacters(self, words: List[str], chars: str) -> int:
#         def can_form(word, chars):
#             char_count = Counter(chars)
#             for char in word:
#                 if char_count[char] <= 0:
#                     return False
#                 char_count[char] -= 1
#             return True
#         result = 0
#         for word in words:
#             if can_form(word, chars):
#                 result += len(word)
#         return result
            
'''
Approach 2: Hash map
1) Create a hash map with frequencies for the characters in chars
2) Iterate through each word in 'words'
3) For each word, create a fequency map
4) check if the word's frequency map is a subset of the chars frequency map
5) if yes, add the length of the word to the result

Time: O(n*m*k), Space: O(k)
'''

# class Solution:
#     def countCharacters(self, words: List[str], chars: str) -> int:
#         result = 0
#         char_count = Counter(chars)
#         for word in words:
#             word_count = Counter(word)
#             if all(word_count[char] <= char_count[char] for char in word):
#                 result += len(word)
#         return result



'''
Approach 3: optimized hash map
1) Create a hash map with frequencies for the characters in chars
2) Iterate through each word in 'words'
3) For each word, decrement the frequency of characters in the map
4) check if any character's frequency becomes negative during the process
5) If no negative frequencies are encountered, add length of word to the result

Time: O(n*m), Space: O(k)
'''

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        result = 0
        char_count = Counter(chars)

        for word in words:
            temp_count = char_count.copy()
            can_form_word = True
            for char in word:
                if temp_count[char] <= 0:
                    can_form_word = False
                    break
                temp_count[char] -= 1

            if can_form_word:
                result += len(word)
        return result
112