Count Words Obtained After Adding a Letter — Medium Problem & Solution

Every string in startWords and targetWords has all distinct letters.

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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue