Count Words Obtained After Adding a Letter

Count Words Obtained After Adding a Letter

What is this problem about?

The Count Words Obtained After Adding a Letter interview question gives you two lists of strings: startWords and targetWords. For each word in targetWords, you want to see if it can be formed by:

1. Choosing a word from startWords.
2. Appending one additional character (not already in the start word).
3. Rearranging the characters into any order. You need to count how many words in targetWords can be obtained this way.

Why is this asked in interviews?

Google uses this Hash Table and Bit Manipulation interview pattern to evaluate your ability to handle sets and permutations efficiently. Since the order of letters doesn't matter, it's about set membership. The challenge is to avoid O(N*M) string comparisons and use an O(N+M) approach with clever encoding.

Algorithmic pattern used

The problem is best solved using Bitmasking or Sorting with a Hash Set.

1. Bitmasking: Since words only contain lowercase English letters, represent each startWord as a 26-bit integer (bitmask). Store all start masks in a Hash Set.
2. Processing Targets: For each targetWord, generate its bitmask.
3. Check Condition: For each character in the targetWord, create a "candidate mask" by removing that character's bit. If this candidate mask exists in the startWords set, the target is obtainable.

Example explanation

startWords = ["abc"], targetWords = ["abcd", "abce"]

1. "abc" mask: 0...0111 (bits for a, b, c). Set: {7}.
2. Target "abcd":
   • Remove 'a': mask for "bcd". Not in set.
   • Remove 'd': mask for "abc". In set! (Match found).
3. Target "abce":
   • Remove 'e': mask for "abc". In set! (Match found). Result: 2.

Common mistakes candidates make

• O(N^2) strings: Comparing every start word with every target word.
• Ignoring the "unique letter" rule: Forgetting that the added letter must not already be in the start word.
• Permutations: Trying to generate all permutations of strings instead of using sorted versions or bitmasks.

Interview preparation tip

Bitmasks are perfect for problems where character order doesn't matter and the alphabet size is small (<= 32 or 64). They allow for O(1) set operations and very low memory usage.