Count Words Obtained After Adding a Letter

Problem Description

You are given two 0-indexed arrays of strings startWords and targetWords. Each string consists of lowercase English letters only. For each string in targetWords, check if it is possible to choose a string from startWords and perform a conversion operation on it to be equal to that from targetWords. The conversion operation involves appending a letter that is not present in the string and rearranging the letters. Return the number of strings in targetWords that can be obtained by performing the operations on any string of startWords.

Key Insights

• You can only append a letter that is not already in the string from startWords.
• The rearrangement of letters allows any order, meaning the target string's letters must be contained in the modified version of the startWords string.
• A set or bitmask can be used to efficiently check the presence of letters in the strings.

Space and Time Complexity

Time Complexity: O(N + M), where N is the length of startWords and M is the length of targetWords. Space Complexity: O(N), for storing the bitmask of letters from startWords.

Solution

To solve the problem, we can use a bit manipulation approach. Each string can be represented as a bitmask, where each bit represents whether a particular letter ('a' to 'z') is present in the string. For each string in startWords, compute its bitmask. For each string in targetWords, also compute its bitmask. The conversion is possible if the bitmask of targetWords has exactly one bit set that is not present in the corresponding startWords bitmask.

1. Create a set to store the bitmasks of startWords.
2. For each targetWords string, compute its bitmask.
3. Check if there exists a startWords bitmask such that it has all bits of the target bitmask except for one additional bit.
4. Count how many targetWords can be formed.

Code Solutions