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.
Transform each word in startWords into a sorted tuple of its characters to leverage the properties of sorted words. This forms a distinct signature that can be stored in a set for quick lookup. For each word in targetWords, remove one character at a time, sort the remaining characters, and check if this signature exists in the startWords set.
This function creates a unique signature for each word by sorting its characters. A set is populated with these signatures for the startWords. The function then iterates through each targetWords word, removing one character at a time, sorting the rest, and checking if this reduced form exists in startSet. The count is incremented for each match found.
Time Complexity: O(NM log M + KM log M), where N is the length of startWords, K is the length of targetWords, M is the maximum word length.
Space Complexity: O(NM), for storing the sorted signatures.
Each character in a word can be represented as a bit in an integer (26 bits for 26 letters). Convert each word into a bitmask representation where each bit denotes the presence of a character. Check if removing one bit from any targetWords bitmask results in a startWords bitmask.
This Java solution uses bit manipulation to represent each word. The getBitmask method creates a bitmask for a word. The function then checks if modifying the bitmask of any targetWords by removing one character (one bit) results in an achievable startWords bitmask. If it exists in the start set of bitmasks, it increases the counter.
Java
JavaScript
Time Complexity: O(NM + KM), where N and K are the sizes of startWords and targetWords, M is the maximum length of a word.
Space Complexity: O(N), for bitmask storage.
We notice that the given strings only contain lowercase letters, and each letter in a string appears at most once. Therefore, we can represent a string with a binary number of length 26, where the i-th bit being 1 indicates that the string contains the i-th lowercase letter, and 0 indicates the absence of the i-th lowercase letter.
We can convert each string in the array startWords into a binary number and store these binary numbers in a set s. For each string in the array targetWords, we first convert it into a binary number, then enumerate each letter in this string, remove this letter from the binary number, and check if there exists a binary number in the set s such that the XOR result of this binary number with the removed letter's binary number is in the set s. If such a binary number exists, then this string can be obtained by performing a transformation operation on some string in startWords, and we increment the answer by one. Then, we skip this string and continue processing the next string.
The time complexity is O(n times |\Sigma|), and the space complexity is O(n). Here, n is the length of the string array targetWords, and |\Sigma| is the size of the character set in the string, which is 26 in this problem.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Set of Sorted Signatures | Time Complexity: O(NM log M + KM log M), where N is the length of startWords, K is the length of targetWords, M is the maximum word length. |
| Bitmask Representation | Time Complexity: O(NM + KM), where N and K are the sizes of startWords and targetWords, M is the maximum length of a word. |
| Hash Table + Bit Manipulation | — |
| 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 |
Count Words Obtained After Adding a Letter | Leetcode 2135 | Contest 275 |String | Bit Masking 🔥🔥🔥 • Coding Decoded • 1,399 views views
Watch 9 more video solutions →Practice Count Words Obtained After Adding a Letter with our built-in code editor and test cases.
Practice on FleetCode