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

&nbsp;
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".


&nbsp;
Constraints:


	1 &lt;= startWords.length, targetWords.length &lt;= 5 * 104
	1 &lt;= startWords[i].length, targetWords[j].length &lt;= 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.


# Brute Force
# O(S * T); S := len(startWors); T := len(targetWords)
# TLE
class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        cnt = 0
        for target in targetWords:
            for start in startWords:
                if len(target) - len(start) == 1 and len(set(list(target)) - set(list(start))) == 1:
                    cnt += 1
                    break
        return cnt

# Sort + HashSet Lookup
# O(S + T) Time
class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        # Sort each start word and add it to a hash set
        startWords_sorted = set()
        # O(S*26*log(26))
        for word in startWords:
            startWords_sorted.add("".join(sorted(list(word))))
        
        # sort each target word and add it to a list
        # O(T*26*log(26))
        targetWords_sorted = []
        for word in targetWords:
            targetWords_sorted.append(sorted(list(word)))
        
        # for each sorted target word, we remove a single character and 
        # check if the resulting word is in the startWords_sorted
        # if it is, we increment cnt and break the inner loop
        # otherwise we keep removing until we either find a hit or reach the
        # end of the string
        # O(T*26) = O(T)
        cnt = 0
        for target in targetWords_sorted:
            for i in range(len(target)):
                w = target[:i] + target[i+1:]
                w = "".join(w)
                if w in startWords_sorted:
                    cnt += 1
                    break
        
        return cnt

# Using Bit Mask
# O(S + T) Time
# Similar algorithm as the one above, implemented using a bit mask to avoid the sorts
class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        start_set = set()
        # O(S * 26)
        for word in startWords:
            m = 0
            for ch in word:
                i = ord(ch) - ord('a')
                m |= (1 << i)
            start_set.add(m)
        
        # O(T * 2 * 26)
        cnt = 0
        for word in targetWords:
            m = 0
            for ch in word:
                i = ord(ch) - ord('a')
                m |= (1 << i)
            
            for ch in word:
                i = ord(ch) - ord('a')
                if m ^ (1 << i) in start_set:
                    cnt += 1
                    break
        return cnt
class Solution {
    public int wordCount(String[] startWords, String[] targetWords) {
        int n = startWords.length;
        int count = 0;
        Set<String> set = new HashSet<>();
        
        //1. store lexicographically sorted letters of startword in set
        for(String start: startWords){
            char[] sAr = start.toCharArray();
            Arrays.sort(sAr);
            set.add(new String(sAr));
        }
        int m = targetWords.length;
        boolean ans = false;
        for(int i = 0; i < m; i++){
            //2. sort lexicographically letters of targetword and store in new string s
            char[] tAr = targetWords[i].toCharArray();
            Arrays.sort(tAr);
            int k = tAr.length;
            String s = String.valueOf(tAr);
            
            ans = false;
            for(int j = 0; j < k; j++){
                //3. make a new string by omitting one letter from word and check if it is present in set than increase count value
                String str = s.substring(0,j) + s.substring(j+1);
                if(set.contains(str)){
                    count++;
                    break;
                }
            }
        }
        return count;    
    }
    
}
class Solution {
public:
    int wordCount(vector<string>& startWords, vector<string>& targetWords) {
        set<vector<int>> hash;
        for (int i = 0; i < startWords.size(); i++) {
            vector<int> counter(26, 0);
            for (char &x : startWords[i]) {
                counter[x - 'a']++;
            }
            hash.insert(counter); 
        }
        
        
        int ans = 0;
        
        for (int i = 0; i < targetWords.size(); i++) {
            vector<int> counter(26, 0);
            for (char &x : targetWords[i]) {
                counter[x - 'a']++;
            }
            
            for (int j = 0; j < 26; j++) {
                if (counter[j] == 1) {
                    counter[j] = 0;
                    
                    if (hash.find(counter) != hash.end()) {
                        ans++;
                        break;
                    }
                    
                    counter[j] = 1;
                }
            }
        }
        
        return ans;
    }
};
var wordCount = function(startWords, targetWords) {
    const startMap = {};
    for(let word of startWords) {
        startMap[word.split('').sort().join('')] = true;
    }

    let ans = 0;
    for(let word of targetWords) {
        for(let i=0;i<word.length;i++) {
            let temp = (word.substring(0,i) + word.substring(i+1,word.length)).split('').sort().join('');
            if(startMap[temp]) {
                ans++;
                break;
            }
        }
    }
    
    return ans;
};
Count Words Obtained After Adding a Letter