Count Words Obtained After Adding a Letter

Medium
641.

Count Words Obtained After Adding a Letter

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.

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 <= 5000
  • 1 <= word length <= 26
  • Each word has all distinct lowercase letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} startWords
 * @param {string[]} targetWords
 * @return {number}
 */
var wordCount = function(startWords, targetWords) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 5000
  • 1 <= word length <= 26
  • Each word has all distinct lowercase letters.

Hints for Count Words Obtained After Adding a Letter

  1. Hint 1

    Rearranging means order is irrelevant — only the set of letters matters.

  2. Hint 2

    A set of distinct lowercase letters fits in a 26-bit integer.

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

  1. Convert every start word to a bitmask and store the masks in a set.
  2. For each target word, compute its mask m.
  3. For each bit b set in m, check whether m ^ (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 m would 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 total

Java

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