# Count Words Obtained After Adding a Letter
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-words-obtained-after-adding-a-letter)
Canonical: https://scaleengineer.com/dsa/problems/count-words-obtained-after-adding-a-letter
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
---
## Problem
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`.

# Approaches
## Using HashSet with Sorted Strings
The core idea is that the order of characters in a word doesn't matter for this problem. "act" is equivalent to "cat". This suggests we can use a canonical representation for each word. A simple canonical form is the string with its characters sorted alphabetically. For example, both "tack" and "actk" become "ackt" when sorted.
A `targetWord` can be formed from a `startWord` if the `targetWord` has one extra character and the rest of the characters are the same as the `startWord`. In terms of our sorted canonical forms, this means if we remove one character from the sorted `targetWord`, the remaining string should be equal to the sorted form of some `startWord`.
To efficiently check for the existence of a sorted `startWord`, we can pre-process all `startWords`, convert them to their sorted form, and store them in a `HashSet`. This allows for quick lookups.
**Time:** O(N * L_s * log(L_s) + M * L_t^2), where N and M are the number of words in `startWords` and `targetWords`, and L_s and L_t are their maximum string lengths. Pre-processing `startWords` takes O(N * L_s * log(L_s)) for sorting. Processing `targetWords` takes O(M * (L_t * log(L_t) + L_t^2)) because for each word we sort it, then loop L_t times, with each loop involving substring creation and hashing which take O(L_t) time. · **Space:** O(N * L_s), where N is the number of `startWords` and L_s is the maximum length of a start word. The `HashSet` stores N strings, each of maximum length L_s.
**Pros:** Much faster than a naive brute-force approach that compares every pair of start and target words.; Conceptually simple, leveraging standard library features like sorting and HashSets.
**Cons:** String sorting and manipulation can be relatively slow compared to integer operations.; Space usage can be high if `startWords` contains many long strings, as the entire sorted strings are stored.
### Explanation
This approach works by first transforming all `startWords` into a canonical form and storing them for efficient access. Since the problem allows rearranging letters, sorting the characters of a string provides a suitable canonical representation.

We iterate through `startWords`, sort each one, and store the result in a `HashSet`. This set, let's call it `startSet`, will contain all possible "base" words in their sorted form.

Then, for each `targetWord`, we want to check if it can be formed by adding a letter to any of the original `startWords`. This is equivalent to checking if removing one letter from the `targetWord` results in a string that matches one of the `startWords`. We apply the same sorting logic to the `targetWord`. For a given `sortedTarget`, we generate all possible predecessor strings by removing one character at a time. If any of these predecessors are found in our `startSet`, it confirms that the `targetWord` is reachable. We increment our count and, to be efficient, immediately move on to the next `targetWord`.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countWords(String[] startWords, String[] targetWords) {
        Set<String> startSet = new HashSet<>();
        for (String word : startWords) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            startSet.add(new String(chars));
        }

        int count = 0;
        for (String word : targetWords) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String sortedTarget = new String(chars);

            for (int i = 0; i < sortedTarget.length(); i++) {
                // Create predecessor by removing character at index i
                String predecessor = sortedTarget.substring(0, i) + sortedTarget.substring(i + 1);
                if (startSet.contains(predecessor)) {
                    count++;
                    break; // Found a match, move to the next targetWord
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a `HashSet<String>` called `startSet`.
*   Iterate through each `word` in `startWords`, sort its characters, and add the resulting string to `startSet`.
*   Initialize a counter `count` to 0.
*   For each `word` in `targetWords`:
    *   Sort the characters of the `word` to get `sortedTarget`.
    *   Iterate through each character of `sortedTarget`.
    *   Create a `predecessor` string by removing the character at the current position.
    *   Check if this `predecessor` string exists in `startSet`.
    *   If it exists, increment `count` and break the inner loop to process the next `targetWord`.
*   Return the final `count`.

## Optimized Approach using Bitmasking
This approach improves upon the previous one by using a more efficient canonical representation for the words. Since each word consists of unique lowercase English letters, we can represent the set of characters in a word using a 26-bit integer, also known as a bitmask. Each bit from 0 to 25 corresponds to a letter from 'a' to 'z'. If a letter is present in the word, its corresponding bit is set to 1; otherwise, it's 0.
For example, the word "act" can be represented by the integer mask `(1 << ('a'-'a')) | (1 << ('c'-'a')) | (1 << ('t'-'a'))`.
This representation is compact and allows for very fast operations. Checking if a `targetWord` can be formed from a `startWord` now becomes a check on their integer bitmasks. Specifically, for a `targetWord`'s mask, we can generate all possible predecessor masks by turning off one bit at a time. If any of these predecessor masks exist in a pre-computed set of `startWord` masks, we've found a match.
**Time:** O(N * L_s + M * L_t), where N and M are the number of words in `startWords` and `targetWords`, and L_s and L_t are their maximum string lengths. Calculating the bitmask for a word takes time proportional to its length. The overall complexity is the sum of time to process all characters in `startWords` and all characters in `targetWords`. · **Space:** O(N), where N is the number of `startWords`. The `HashSet` stores at most N integers, which is very memory-efficient.
**Pros:** Highly efficient in both time and space due to the use of bitmasking.; Integer operations and lookups are much faster than string manipulations and sorting.
**Cons:** The bitmasking technique is specific to problems with a small, fixed alphabet and constraints like unique characters. It's less general than the sorting approach.
### Explanation
This optimized solution leverages bitmasking to create a unique and efficient integer representation for each word. The presence of each of the 26 lowercase letters is mapped to a bit in an integer.

First, we process all `startWords`. For each word, we calculate its bitmask by iterating through its characters and setting the corresponding bits. These integer masks are stored in a `HashSet` for O(1) average time lookups.

Next, we iterate through the `targetWords`. For each `targetWord`, we also compute its bitmask. Then, to check if it can be formed from a `startWord`, we try removing each of its characters one by one. In the bitmask world, removing a character is equivalent to turning off its corresponding bit. We can do this efficiently using the XOR operation (`^`). For each potential predecessor mask generated, we check if it exists in our set of `startWord` masks. If a match is found, we increment our count and move to the next `targetWord`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countWords(String[] startWords, String[] targetWords) {
        Set<Integer> startMasks = new HashSet<>();
        for (String word : startWords) {
            startMasks.add(getBitmask(word));
        }

        int count = 0;
        for (String word : targetWords) {
            int targetMask = getBitmask(word);
            // Iterate through each character of the target word to find a predecessor
            for (char c : word.toCharArray()) {
                // To remove a character, we turn off its corresponding bit.
                // Using XOR is a neat trick for this since the bit is guaranteed to be set.
                int predecessorMask = targetMask ^ (1 << (c - 'a'));
                if (startMasks.contains(predecessorMask)) {
                    count++;
                    break; // Found a match, move to the next targetWord
                }
            }
        }
        return count;
    }

    private int getBitmask(String word) {
        int mask = 0;
        for (char c : word.toCharArray()) {
            mask |= (1 << (c - 'a'));
        }
        return mask;
    }
}
```
### Algorithm
*   Initialize a `HashSet<Integer>` called `startMasks`.
*   For each `word` in `startWords`:
    *   Compute its integer bitmask representation.
    *   Add the bitmask to `startMasks`.
*   Initialize a counter `count` to 0.
*   For each `word` in `targetWords`:
    *   Compute its bitmask, `targetMask`.
    *   For each character `c` in the `word`:
        *   Calculate a `predecessorMask` by turning off the bit corresponding to `c` in `targetMask`.
        *   Check if `predecessorMask` exists in `startMasks`.
        *   If it does, increment `count` and break to process the next `targetWord`.
*   Return `count`.

# Solutions
### Java

```java
class Solution {
public
  int wordCount(String[] startWords, String[] targetWords) {
    Set<Integer> s = new HashSet<>();
    for (String word : startWords) {
      int mask = 0;
      for (char c : word.toCharArray()) {
        mask |= (1 << (c - 'a'));
      }
      s.add(mask);
    }
    int ans = 0;
    for (String word : targetWords) {
      int mask = 0;
      for (char c : word.toCharArray()) {
        mask |= (1 << (c - 'a'));
      }
      for (char c : word.toCharArray()) {
        int t = mask ^ (1 << (c - 'a'));
        if (s.contains(t)) {
          ++ans;
          break;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int wordCount(vector<string> &startWords, vector<string> &targetWords) {
    unordered_set<int> s;
    for (auto &word : startWords) {
      int mask = 0;
      for (char c : word)
        mask |= (1 << (c - 'a'));
      s.insert(mask);
    }
    int ans = 0;
    for (auto &word : targetWords) {
      int mask = 0;
      for (char c : word)
        mask |= (1 << (c - 'a'));
      for (char c : word) {
        int t = mask ^ (1 << (c - 'a'));
        if (s.count(t)) {
          ++ans;
          break;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int: s = set() for word in startWords: mask = 0 for c in word: mask |= 1 << (ord(c) - ord('a')) s . add(mask) ans = 0 for word in targetWords: mask = 0 for c in word: mask |= 1 << (ord(c) - ord('a')) for c in word: t = mask ^ (1 << (ord(c) - ord('a'))) if t in s: ans += 1 break return ans

```