LeetCode 1160 - Find Words That Can Be Formed by Characters

LeetCode Problem 1160

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String, Counting

Solution

Problem Understanding

This problem asks us to determine which words from a given list can be constructed using the characters available in another string, chars. A word is considered good if every character it needs exists in chars in sufficient quantity. Importantly, characters in chars can only be used once per word, meaning repeated letters matter.

For example, if chars = "atach" and a word is "cat", the word is valid because the letters c, a, and t all exist in chars. However, if a word is "tree", it is invalid because "tree" requires two 'e' characters, while chars contains none.

The input consists of:

• words, an array of lowercase English strings.
• chars, a string containing available lowercase English characters.

The goal is not to return the valid words themselves, but rather the sum of the lengths of all good words.

The constraints are relatively small:

• At most 1000 words.
• Each word has length at most 100.
• chars also has length at most 100.

These limits suggest that an efficient counting-based approach will easily fit within performance requirements. Since the alphabet contains only lowercase English letters, there are only 26 possible characters. This observation strongly hints that character frequency counting is a natural fit.

Several edge cases are important to consider upfront. A word may require repeated characters, such as "hello" needing two 'l' characters, so checking only character existence is not enough. Some words may be longer than chars, making them impossible to form immediately. Words may share letters, but each word is checked independently, meaning characters are not consumed globally across all words. The problem guarantees non-empty input and lowercase English letters only, so we do not need to handle invalid input formats or uppercase characters.

Approaches

Brute Force Approach

A straightforward approach is to check each word character by character against chars. For every word, we could make a mutable copy of chars, then try removing characters as they are matched.

For example, to check "cat" against "atach", we search for 'c', remove it, search for 'a', remove it, and so on. If at any point a character cannot be found, the word is invalid.

This works because it directly simulates the problem requirement that each character can only be used once. However, searching and removing characters repeatedly is inefficient. String removal is expensive, and repeated scans make the solution slower than necessary.

The key inefficiency is that we repeatedly recompute character availability for every lookup.

Optimal Approach

The key insight is that what really matters is character frequency, not character order.

Instead of repeatedly searching through chars, we first count how many times each character appears. Then, for every word, we count its character frequencies and compare them against the available frequencies in chars.

If every character in the word appears no more times than in chars, the word is valid and we add its length to the answer.

Since there are only 26 lowercase English letters, frequency comparison is extremely efficient. We can represent counts using either hash maps or fixed-size arrays of length 26.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(W × L × C)	O(C)	For each word, repeatedly searches and removes characters from chars
Optimal	O(W × (L + 26))	O(26)	Uses character frequency counting for efficient validation

Where:

• W = number of words
• L = average word length
• C = length of chars

Since 26 is constant, the optimal approach effectively runs in linear time relative to the total input size.

Algorithm Walkthrough

1. Create a frequency count of chars.

We first count how many times each letter appears in chars. Since only lowercase English letters are allowed, we use an array of size 26, where index 0 represents 'a', index 1 represents 'b', and so on.

This preprocessing step gives us a reusable inventory of available characters. 2. Initialize a variable to store the total length.

We maintain an integer total_length, which starts at 0. Whenever we find a valid word, we add its length to this total. 3. Process each word independently.

For every word in words, create another frequency array of size 26 to count how many times each character appears in that word.

This step is necessary because repeated letters matter. For example, "book" requires two 'o' characters. 4. Compare the word frequency with the available frequency.

Check each of the 26 character positions.

If the word requires more of any character than chars provides, the word is invalid and we stop checking it immediately.

If all character counts are within limits, the word is valid. 5. Add the word length if valid.

If the word passed validation, add len(word) to total_length. 6. Return the final answer.

After processing all words, return total_length.

Why it works

The algorithm works because it directly enforces the defining property of a good word: every character must exist in chars with sufficient frequency.

For each word, we compare required counts against available counts. If every required count is less than or equal to availability, then the word can be formed exactly. If even one character exceeds availability, construction becomes impossible.

Because every word is checked independently and all character constraints are verified, the final sum is guaranteed to be correct.

Python Solution

from typing import List

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

        for ch in chars:
            char_count[ord(ch) - ord('a')] += 1

        total_length = 0

        for word in words:
            word_count = [0] * 26

            for ch in word:
                word_count[ord(ch) - ord('a')] += 1

            is_good = True

            for i in range(26):
                if word_count[i] > char_count[i]:
                    is_good = False
                    break

            if is_good:
                total_length += len(word)

        return total_length

The implementation begins by creating a fixed-size frequency array for chars. Each character increments the corresponding index based on its alphabetical position.

Next, we iterate through every word. For each word, we build another frequency array representing the letters required to form that word.

After counting the word's characters, we compare its requirements against the available inventory stored in char_count. If any character requirement exceeds availability, we mark the word as invalid and stop checking immediately using break.

If the word passes all checks, we add its length to total_length.

Finally, once all words are processed, we return the accumulated result.

Go Solution

func countCharacters(words []string, chars string) int {
	charCount := make([]int, 26)

	for _, ch := range chars {
		charCount[ch-'a']++
	}

	totalLength := 0

	for _, word := range words {
		wordCount := make([]int, 26)

		for _, ch := range word {
			wordCount[ch-'a']++
		}

		isGood := true

		for i := 0; i < 26; i++ {
			if wordCount[i] > charCount[i] {
				isGood = false
				break
			}
		}

		if isGood {
			totalLength += len(word)
		}
	}

	return totalLength
}

The Go implementation closely mirrors the Python solution. Since the problem guarantees lowercase English letters, a fixed integer slice of length 26 is used for counting frequencies.

One Go-specific detail is that iterating over strings with range produces runes. Because all input characters are lowercase English letters, subtracting 'a' safely produces indices between 0 and 25.

There are no special nil handling concerns because the problem guarantees valid non-empty input. Integer overflow is also not a concern due to the small constraint sizes.

Worked Examples

Example 1

Input:

words = ["cat","bt","hat","tree"]
chars = "atach"

First, build the frequency count for chars.

Character	Count
a	2
c	1
h	1
t	1

All other letters have count 0.

Now process each word.

Word	Word Count	Valid?	Running Total
"cat"	c=1, a=1, t=1	Yes	3
"bt"	b=1, t=1	No, no b	3
"hat"	h=1, a=1, t=1	Yes	6
"tree"	t=1, r=1, e=2	No, missing e and r	6

Final answer:

6

Example 2

Input:

words = ["hello","world","leetcode"]
chars = "welldonehoneyr"

Character counts in chars include:

Character	Count
w	1
e	3
l	2
d	1
o	2
n	2
h	1
y	1
r	1

Now evaluate each word.

Word	Required Characters	Valid?	Running Total
"hello"	h=1, e=1, l=2, o=1	Yes	5
"world"	w=1, o=1, r=1, l=1, d=1	Yes	10
"leetcode"	requires c=1 and extra e	No	10

Final answer:

10

Complexity Analysis

Measure	Complexity	Explanation
Time	O(W × (L + 26))	Count characters for each word, then compare against 26 letters
Space	O(26)	Fixed-size frequency arrays

The preprocessing step for chars takes O(C) time, where C is the length of chars.

For each word, we spend O(L) time counting letters and O(26) time validating counts. Since 26 is constant, this simplifies to linear time with respect to total word length.

The space complexity is constant because both char_count and word_count always have exactly 26 entries, regardless of input size.

Test Cases

solution = Solution()

# Provided example 1
assert solution.countCharacters(
    ["cat", "bt", "hat", "tree"],
    "atach"
) == 6  # basic example with valid and invalid words

# Provided example 2
assert solution.countCharacters(
    ["hello", "world", "leetcode"],
    "welldonehoneyr"
) == 10  # repeated characters

# Single valid word
assert solution.countCharacters(
    ["abc"],
    "abc"
) == 3  # exact match

# Single invalid word
assert solution.countCharacters(
    ["abc"],
    "ab"
) == 0  # missing character

# Multiple repeated letters
assert solution.countCharacters(
    ["book", "cook", "look"],
    "bookcl"
) == 4  # only "book" works

# Empty result
assert solution.countCharacters(
    ["aaa", "bbb"],
    "ab"
) == 0  # no word can be formed

# Duplicate valid words
assert solution.countCharacters(
    ["a", "a", "a"],
    "a"
) == 3  # each word checked independently

# Word longer than chars
assert solution.countCharacters(
    ["abcdef"],
    "abc"
) == 0  # impossible due to length

# Maximum repeated character requirement
assert solution.countCharacters(
    ["aaaa", "aaa"],
    "aaa"
) == 3  # only one word valid

# Boundary case with single character
assert solution.countCharacters(
    ["a"],
    "a"
) == 1  # smallest valid input

Test	Why
["cat","bt","hat","tree"], "atach"	Validates standard mixed-case behavior
["hello","world","leetcode"], "welldonehoneyr"	Tests repeated characters
["abc"], "abc"	Exact match case
["abc"], "ab"	Missing character case
["book","cook","look"], "bookcl"	Verifies repeated letter handling
["aaa","bbb"], "ab"	Ensures zero result is handled
["a","a","a"], "a"	Confirms words are checked independently
["abcdef"], "abc"	Tests longer word impossibility
["aaaa","aaa"], "aaa"	Repeated character limit
["a"], "a"	Minimum boundary input

Edge Cases

Words with repeated characters

A common source of bugs is checking only whether a character exists instead of verifying how many times it appears. For example, "hello" requires two 'l' characters. If chars contains only one 'l', the word must be rejected. The implementation handles this correctly by comparing frequency counts rather than simple membership.

Words checked independently

A naive interpretation might mistakenly consume characters globally across all words. For example, if chars = "a" and words = ["a", "a"], both words are valid because each word gets a fresh check against chars. The implementation correctly rebuilds word_count for every word and never mutates char_count.

Words longer than chars

A word that is longer than chars cannot possibly be formed. Although the algorithm does not explicitly check lengths, it naturally handles this case during frequency comparison. Eventually, at least one character count exceeds availability, causing the word to be rejected.

Missing characters entirely

Some words may require letters that do not exist in chars at all. For example, "cat" cannot be formed from "ab". Since unavailable letters have a count of 0 in char_count, the comparison immediately fails, ensuring correctness without any special handling.