Skip to main content
Talentd

Count Words Obtained After Adding a Letter - Solution & Explanation

MediumArrayHash TableStringBit Manipulation15 min readAsked at: Google
Practice this problem

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:

  1. 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".
  2. 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.

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 * 104
  • 1 <= startWords[i].length, targetWords[j].length <= 26
  • Each string of startWords and targetWords consists of lowercase English letters only.
  • No letter occurs more than once in any string of startWords or targetWords.

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.

Approach 1: Set of Sorted Signatures

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Bitmask Representation

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Hash Table + Bit Manipulation

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(NM), for storing the sorted signatures.

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.
Space Complexity: O(N), for bitmask storage.

Hash Table + Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Set of Sorted SignaturesO(S * k log k + T * k^2 log k)O(S * k)When using straightforward string normalization and sorting is acceptable
Bitmask RepresentationO((S + T) * 26)O(S)Preferred optimal approach for interviews and large inputs

Video Solution

Count Words Obtained After Adding a Letter | Leetcode 2135 | Contest 275 |String | Bit Masking 🔥🔥🔥 • Coding Decoded • 1,410 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Words Obtained After Adding a Letter easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 44%. The challenge comes from recognizing that character order does not matter and converting the problem into a normalized representation such as sorted strings or bitmasks.
Count Words Obtained After Adding a Letter Python/Java solution
Python solutions commonly use sorted signatures with a set for simplicity, while Java implementations often prefer the bitmask approach for performance. Both methods rely on hash sets for constant-time lookups and iterate through each target word while removing one character or bit.
How to solve Count Words Obtained After Adding a Letter in O(n)?
Use a bitmask to represent the characters in each word. Insert masks of startWords into a hash set. For every target word, compute its mask and attempt removing each letter by clearing one bit. If any resulting mask exists in the set, the target word can be formed. This makes the algorithm close to linear with respect to the number of words.
What is the best approach for Count Words Obtained After Adding a Letter?
The most efficient approach uses bitmask representation. Each word is encoded as a 26-bit integer where each bit corresponds to a letter. Store masks for startWords in a hash set, then for each target word remove one bit at a time and check if the resulting mask exists. This reduces the problem to constant-time bit operations and hash lookups.
Is Count Words Obtained After Adding a Letter asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving hashing, bit manipulation, and string normalization. Variants of this problem have appeared in interviews at companies like Google, Amazon, and Meta because they test efficient set lookups and bit-level optimizations.
What data structure is used in Count Words Obtained After Adding a Letter?
A hash set is the primary data structure used to store normalized representations of start words. Depending on the approach, the stored values are either sorted string signatures or integer bitmasks representing letter presence.
What is the time complexity of Count Words Obtained After Adding a Letter?
The optimal bitmask solution runs in O((S + T) * 26) time, where S is the number of start words and T is the number of target words. Each word requires building a mask and checking up to 26 possible bit removals. Space complexity is O(S) for storing the start word masks.

Ready to solve this problem?

Practice Count Words Obtained After Adding a Letter with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Substrings That Differ by One Character

Next

Maximum Score From Removing Substrings