Watch 10 video solutions for Count Words Obtained After Adding a Letter, a medium level problem involving Array, Hash Table, String. This walkthrough by Coding Decoded has 1,399 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 is described in the following two steps:
"abc", the letters 'd', 'e', or 'y' can be added to it, but not 'a'. If 'd' is added, the resulting string will be "abcd"."abcd" can be rearranged to "acbd", "bacd", "cbda", and so on. Note that it can also be rearranged to "abcd" itself.Return the number of strings in targetWords that can be obtained by performing the operations on any string of startWords.
Note that you will only be verifying if the string in targetWords can be obtained from a string in startWords by performing the operations. The strings in startWords do not actually change during this process.
Example 1:
Input: startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"] Output: 2 Explanation: - In order to form targetWords[0] = "tack", we use startWords[1] = "act", append 'k' to it, and rearrange "actk" to "tack". - There is no string in startWords that can be used to obtain targetWords[1] = "act". Note that "act" does exist in startWords, but we must append one letter to the string before rearranging it. - In order to form targetWords[2] = "acti", we use startWords[1] = "act", append 'i' to it, and rearrange "acti" to "acti" itself.
Example 2:
Input: startWords = ["ab","a"], targetWords = ["abc","abcd"] Output: 1 Explanation: - In order to form targetWords[0] = "abc", we use startWords[0] = "ab", add 'c' to it, and rearrange it to "abc". - There is no string in startWords that can be used to obtain targetWords[1] = "abcd".
Constraints:
1 <= startWords.length, targetWords.length <= 5 * 1041 <= startWords[i].length, targetWords[j].length <= 26startWords and targetWords consists of lowercase English letters only.startWords or targetWords.Problem Overview: You receive two arrays: startWords and targetWords. A target word is valid if you can take a word from startWords, add exactly one letter, and then rearrange the characters to match the target. The task is to count how many target words can be produced this way.
Approach 1: Set of Sorted Signatures (O(S * k log k + T * k^2 log k) time, O(S * k) space)
This approach normalizes words using sorted character signatures. For every word in startWords, sort its characters and store the result in a set for O(1) membership checks. For each word in targetWords, remove one character at every index, sort the remaining characters, and check whether the resulting signature exists in the set. If any removal matches a stored start signature, the target word is achievable.
The key idea: rearranging characters means only the multiset of letters matters. Sorting converts every word into a canonical representation. The set lookup avoids scanning the entire start list. This solution relies on sorting and a hash table for efficient lookups.
Approach 2: Bitmask Representation (O((S + T) * 26) time, O(S) space)
A more efficient technique encodes each word as a 26-bit integer mask where bit i represents whether letter 'a' + i appears. Build a hash set of masks for all startWords. For every targetWord, compute its mask, then try removing each set bit (simulating the removal of the added letter). If the resulting mask exists in the start set, the target word can be formed.
This works because each letter appears at most once in valid transformations. Bit operations make checking subsets extremely fast. Instead of sorting strings repeatedly, you perform constant-time bit manipulations and hash lookups. The method combines bit manipulation with a hash table, reducing the complexity to roughly linear in the number of words.
Recommended for interviews: The bitmask approach is the expected optimal solution. It demonstrates strong understanding of character encoding and efficient set membership checks. The sorted-signature approach is still valuable during interviews because it shows clear reasoning about normalization and hashing before optimizing further.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set of Sorted Signatures | O(S * k log k + T * k^2 log k) | O(S * k) | When using straightforward string normalization and sorting is acceptable |
| Bitmask Representation | O((S + T) * 26) | O(S) | Preferred optimal approach for interviews and large inputs |