Find Words That Can Be Formed by Characters

Find Words That Can Be Formed by Characters

1. What is this problem about?

The Find Words That Can Be Formed by Characters interview question is a resource-limited string matching task. You are given a list of words and a string of available chars. A word is "good" if it can be formed by characters from chars (each character can only be used as many times as it appears in chars). You need to return the sum of the lengths of all good words.

2. Why is this asked in interviews?

Companies like Apple and PayPal ask the Find Words That Can Be Formed coding problem to evaluate your proficiency with Hash Table interview patterns. It evaluations whether you can use frequency maps to efficiently compare the character requirements of a word against a fixed pool of resources.

3. Algorithmic pattern used

This problem follows the Frequency Counting pattern.

1. Pool Count: Create a frequency map (or an array of size 26) for the chars string.
2. Word Count: For each word in the words list:
   • Create a frequency map for that specific word.
   • Compare the word's map with the pool's map. If for every character, wordCount[char] <= poolCount[char], the word is good.
3. Summation: Add the length of every "good" word to a running total.

4. Example explanation

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

• chars map: {a:2, t:1, c:1, h:1}
• "cat": {c:1, a:1, t:1}. (All counts $\leq$ chars map). Good! (Length 3).
• "bt": {b:1, t:1}. ('b' is not in chars). Not Good.
• "hat": {h:1, a:1, t:1}. (All counts $\leq$ chars map). Good! (Length 3). Total: $3 + 3 = 6$.

5. Common mistakes candidates make

• Modifying the original map: Decrementing counts in the main chars map while checking a word, which ruins the check for subsequent words. Always use a copy or compare counts directly.
• Nested Loops: Using $O( ext{word\_length} imes ext{chars\_length})$ for every word instead of the $O(N)$ frequency map approach.
• Sorting: Sorting every word and the chars string ($O(N \log N)$), which is slower than counting ($O(N)$).

6. Interview preparation tip

For alphabet-related problems (a-z), an array of size 26 is almost always better than a Hash Map. It provides $O(1)$ access with a very small constant factor and is a common optimization noted by experienced candidates in Hash Table interview patterns.