Find Words That Can Be Formed by Characters

Difficulty: Easy | Acceptance: 71.60% | Paid: No Topics: Array, Hash Table, String, Counting

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.

• Examples
• Constraints
• Hash Map Frequency Counting
• Fixed Array Counting
• Sorting and Two Pointers

Examples

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 consist of lowercase English letters.

Hash Map Frequency Counting

Intuition We can count the frequency of each character available in chars using a hash map. Then, for each word in words, we count its character frequencies and check if the chars map contains at least that many of each character.

Steps

• Create a frequency map for the string chars.
• Iterate through each word in the words array.
• For each word, create a temporary frequency map.
• Compare the temporary map with the chars map. If the count for any character in the word exceeds the count in chars, the word cannot be formed.
• If the word is valid, add its length to the result sum.

from collections import Counter
from typing import List

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        chars_count = Counter(chars)
        res = 0
        for w in words:
            w_count = Counter(w)
            if all(w_count[c] <= chars_count.get(c, 0) for c in w_count):
                res += len(w)
        return res

Complexity

• Time: O(N * L), where N is the number of words and L is the average length of a word. We iterate through every character to build maps.
• Space: O(1) or O(K), where K is the size of the character set (26 for lowercase English letters). The space used for the hash maps is constant relative to the input size.
• Notes: Hash maps provide flexible counting but have slightly more overhead than arrays.

Fixed Array Counting

Intuition Since the problem states that strings consist only of lowercase English letters, we can optimize the Hash Map approach by using a fixed-size integer array of length 26. This reduces overhead and improves cache locality.

Steps

• Create an integer array counts of size 26, initialized to 0.
• Iterate through chars and increment the index corresponding to each character (e.g., index = char - 'a').
• Iterate through each word in words.
• For each word, create a temporary array wordCounts of size 26.
• Iterate through the word, incrementing the corresponding index in wordCounts.
• Compare wordCounts with counts. If wordCounts[i] > counts[i] for any index i, the word is invalid.
• If valid, add the word’s length to the result.

from typing import List

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        counts = [0] * 26
        for c in chars:
            counts[ord(c) - ord('a')] += 1
        
        res = 0
        for w in words:
            w_counts = [0] * 26
            for c in w:
                w_counts[ord(c) - ord('a')] += 1
            
            if all(w_counts[i] <= counts[i] for i in range(26)):
                res += len(w)
        return res

Complexity

• Time: O(N * L), where N is the number of words and L is the average length of a word.
• Space: O(1), as the array size is fixed at 26 regardless of input size.
• Notes: This is generally the fastest approach for this problem due to low overhead and direct memory access.

Sorting and Two Pointers

Intuition We can sort the chars string and each word. Then, we can use a two-pointer technique to check if the sorted word is a subsequence (in terms of character counts) of the sorted chars string.

Steps

• Sort the chars string.
• Initialize the result sum to 0.
• Iterate through each word in words.
• Sort the current word.
• Use two pointers: one for the sorted chars (i) and one for the sorted word (j).
• While both pointers are within bounds:
  • If chars[i] == word[j], increment both pointers (we found a match).
  • If chars[i] < word[j], increment i (current char in chars is too small).
  • If chars[i] > word[j], the word cannot be formed (break).
• If we successfully traverse the entire word (j == word.length), the word is good. Add its length to the result.

from typing import List

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        sorted_chars = sorted(chars)
        res = 0
        
        for w in words:
            sorted_w = sorted(w)
            i = j = 0
            while i < len(sorted_chars) and j < len(sorted_w):
                if sorted_chars[i] == sorted_w[j]:
                    j += 1
                i += 1
            
            if j == len(sorted_w):
                res += len(w)
        return res

Complexity

• Time: O(N * L log L), where N is the number of words and L is the average length of a word. Sorting each word dominates the time complexity.
• Space: O(L) to store the sorted version of the strings (or O(1) if sorting in-place).
• Notes: This approach is less efficient than counting (O(N * L)) because of the sorting overhead.