Count Words Obtained After Adding a Letter - Video Solutions
Count Words Obtained After Adding a Letter | Leetcode 2135 | Contest 275 |String | Bit Masking 🔥🔥🔥
Count Words Obtained After Adding a Letter - Video Solution
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,410 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- Append any lowercase letter that is not present in the string to its end.
- For example, if the string is
"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".
- For example, if the string is
- Rearrange the letters of the new string in any arbitrary order.
- For example,
"abcd"can be rearranged to"acbd","bacd","cbda", and so on. Note that it can also be rearranged to"abcd"itself.
- For example,
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 <= 26- Each string of
startWordsandtargetWordsconsists of lowercase English letters only. - No letter occurs more than once in any string of
startWordsortargetWords.
Approach Overview
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.
Complexity Analysis
| 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 |