We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Words That Can Be Formed by Characters

Difficulty: Easy

Problem Description

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.

Key Insights

  • Each character in chars can be used only once to form a valid word.
  • The solution requires counting the frequency of each character in chars and comparing it against the character counts in each word.
  • The approach involves iterating through each word, checking if it can be composed of the available characters.

Space and Time Complexity

Time Complexity: O(N * M) where N is the number of words and M is the maximum length of a word.
Space Complexity: O(1) for the character frequency map since we are dealing with a fixed set of 26 lowercase letters.

Solution

To solve the problem, we can use a frequency counting approach. We will create a frequency map for the characters in chars and then for each word, check if it can be formed using the characters in the map. If it can, we add its length to the total sum.

  1. Count the frequency of each character in chars.
  2. For each word in words, count its characters.
  3. Verify if the word can be formed by comparing its character counts with the frequency counts from chars.
  4. Sum the lengths of all valid words.

Code Solutions

def countCharacters(words, chars):
    # Create a frequency map for chars
    char_count = {}
    for char in chars:
        char_count[char] = char_count.get(char, 0) + 1
    
    total_length = 0
    
    # Check each word
    for word in words:
        word_count = {}
        for char in word:
            word_count[char] = word_count.get(char, 0) + 1
        
        # Check if the word can be formed
        is_good = True
        for char in word_count:
            if word_count[char] > char_count.get(char, 0):
                is_good = False
                break
        
        if is_good:
            total_length += len(word)
    
    return total_length
← Back to All Questions