Count Words Obtained After Adding a Letter — Solution
Count Words Obtained After Adding a Letter solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Words Obtained After Adding a Letter is a medium coding problem on strings, hash table and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Bit Manipulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Every string in startWords and targetWords has all distinct letters.
A target word is obtainable if you can take some start word, append one letter it does not already contain, and then rearrange the result into the target.
Return how many target words are obtainable. Start words are never consumed — each can be reused.
Example 1
Input: startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"]
Output: 2
Explanation: "tack" comes from "act" plus k; "acti" comes from "act" plus i. "act" itself needs a start word of length 2 that does not exist here.
Example 2
Input: startWords = ["ab","a"], targetWords = ["abc","abcd"]
Output: 1
Explanation: "abc" comes from "ab" plus c; "abcd" would need a three-letter start word.
Example 3
Input: startWords = ["kai"], targetWords = ["kair","ikar","xyz"]
Output: 2
Constraints
1 <= startWords.length, targetWords.length <= 50001 <= word length <= 26Each word has all distinct lowercase letters.
Hints for Count Words Obtained After Adding a Letter
Hint 1
Rearranging means order is irrelevant — only the set of letters matters.
Hint 2
A set of distinct lowercase letters fits in a 26-bit integer.
Hint 3
For each target, remove one letter at a time and ask whether the remaining set is a start word.
How to solve Count Words Obtained After Adding a Letter
Since letters are distinct and order does not matter, each word is exactly a 26-bit set. 'Append one letter' becomes 'the target's mask with one bit cleared is a start word's mask'.
Approach
- Convert every start word to a bitmask and store the masks in a set.
- For each target word, compute its mask
m. - For each bit
bset inm, check whetherm ^ (1 << b)is in the set; one hit means the target is obtainable.
Why it works
Clearing bit b from the target's mask is precisely the letter-set of the start word that would have had b appended. Because all letters are distinct, the mask determines the multiset of letters uniquely, so mask equality is the same as being an anagram.
Complexity
- Time —
O(26 · (S + T)) - Space —
O(S)
Pitfalls
- Comparing sorted strings instead of masks also works but is slower and easier to get wrong on lengths.
- Iterating over all 26 bits rather than only the bits set in
mwould test removing a letter the target does not have. - Counting a target more than once if several removals hit — break after the first success.
Reference solution
Python
from typing import List
def wordCount(startWords: List[str], targetWords: List[str]) -> int:
def mask(w: str) -> int:
m = 0
for c in w:
m |= 1 << (ord(c) - 97)
return m
have = set(mask(w) for w in startWords)
total = 0
for t in targetWords:
m = mask(t)
for b in range(26):
if (m >> b) & 1 and (m ^ (1 << b)) in have:
total += 1
break
return totalJava
public static int wordCount(String[] startWords, String[] targetWords) {
Set<Integer> have = new HashSet<>();
for (String w : startWords) {
int m = 0;
for (int i = 0; i < w.length(); i++) m |= 1 << (w.charAt(i) - 'a');
have.add(m);
}
int total = 0;
for (String t : targetWords) {
int m = 0;
for (int i = 0; i < t.length(); i++) m |= 1 << (t.charAt(i) - 'a');
for (int b = 0; b < 26; b++) {
if ((m & (1 << b)) != 0 && have.contains(m ^ (1 << b))) { total++; break; }
}
}
return total;
}C++
int wordCount(vector<string>& startWords, vector<string>& targetWords) {
unordered_set<int> have;
for (const string& w : startWords) {
int m = 0;
for (char c : w) m |= 1 << (c - 'a');
have.insert(m);
}
int total = 0;
for (const string& t : targetWords) {
int m = 0;
for (char c : t) m |= 1 << (c - 'a');
for (int b = 0; b < 26; b++) {
if ((m & (1 << b)) && have.count(m ^ (1 << b))) { total++; break; }
}
}
return total;
}JavaScript
var wordCount = function(startWords, targetWords) {
var mask = function(w) {
var m = 0;
for (var i = 0; i < w.length; i++) m |= 1 << (w.charCodeAt(i) - 97);
return m;
};
var have = {};
for (var s = 0; s < startWords.length; s++) have[String(mask(startWords[s]))] = true;
var total = 0;
for (var t = 0; t < targetWords.length; t++) {
var m = mask(targetWords[t]);
for (var b = 0; b < 26; b++) {
if ((m & (1 << b)) !== 0 && have[String(m ^ (1 << b))] === true) { total++; break; }
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets