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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Words That Can Be Formed by Characters

Number: 1112

Difficulty: Easy

Paid? No

Companies: Karat, Amazon

Problem Description

Given an array of strings words and a string chars, determine which words can be formed using the characters from chars (each character can only be used once per word). Return the sum of the lengths of all such words that can be formed.

Key Insights

  • Use a frequency count (hash table or fixed-size array) to count characters in chars.
  • For each word, count the frequency of its characters and compare with the frequency in chars.
  • Only add the word’s length to the result if every character appears enough times in chars.

Space and Time Complexity

Time Complexity: O(n * L), where n is the number of words and L is the maximum length of the words. Space Complexity: O(1) since the frequency count is limited to 26 lowercase English letters.

Solution

We start by counting the frequency of each character in the given string chars using a hash table (or fixed-size array for 26 letters). Then, for each word in words, we create a similar frequency count. We compare both counts to ensure that for each character in the word, the count needed is less than or equal to the available count in chars. If the word can be formed, we add its length to our total sum. This approach efficiently handles the constraints given.

Code Solutions

# Python implementation

def countCharacters(words, chars):
    # Count frequencies of each character in chars
    chars_count = {}
    for ch in chars:
        chars_count[ch] = chars_count.get(ch, 0) + 1

    total_length = 0
    # Check each word in words
    for word in words:
        word_count = {}
        # Count frequency of each character in the word
        for ch in word:
            word_count[ch] = word_count.get(ch, 0) + 1

        # Verify if the word can be formed by comparing counts
        can_form = True
        for ch in word_count:
            if word_count[ch] > chars_count.get(ch, 0):
                can_form = False
                break
        
        # If the word is valid, add its length to the total sum
        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
← Back to All Questions