algoadvance

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). 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
• All strings contain lowercase English letters only.

---

Clarifying Questions

1. Do we need to consider the frequency of characters in chars when forming words?
   Yes, each character in chars can only be used as many times as it appears in chars.

2. Should we assume that all inputs contain only lowercase English letters?
   Yes, based on the problem statement.

---

Strategy

1. Count the Frequency of Characters in the chars String:
   Use Python’s collections.Counter to count the frequency of each character in chars.

2. Check Each Word:
   For each word in words, count the frequency of each character. Check if each character in the word can be formed using the characters in chars by comparing their counts.

3. Sum the Lengths of Valid Words:
   If a word can be formed from chars, add its length to the sum.

Time Complexity

• Counting characters in chars takes (O(C)) where (C) is the length of chars.
• For each word, counting characters takes (O(W)) where (W) is the length of the word.
• Checking if a word can be formed takes (O(W)) as well.
• Overall, the complexity is (O(N * W)) where:
  • (N) is the number of words.
  • (W) is the average length of the words.

---

Code

from collections import Counter

def countCharacters(words, chars):
    # Step 1: Count the frequency of each character in chars
    char_count = Counter(chars)
    total_length = 0
    
    # Step 2: Process each word in words
    for word in words:
        word_count = Counter(word)
        
        # Check if the word can be formed by comparing character counts
        can_form = True
        for char in word_count:
            if word_count[char] > char_count.get(char, 0):
                can_form = False
                break
        
        # If the word can be formed, add its length to total_length
        if can_form:
            total_length += len(word)
    
    return total_length

# Example usage
words = ["cat","bt","hat","tree"]
chars = "atach"
print(countCharacters(words, chars))  # Output: 6

This code correctly implements the solution by counting character frequencies and verifying each word against the available characters in chars. The strategy ensures that we handle each word only in linear time relative to its length, making the solution efficient given the problem constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?