Word Pairs With No Shared Letters
Problem
A puzzle setter wants two clue words that share no letter at all, and the longer the pair the better. Given a list of lowercase words, return the largest value of len(a) * len(b) over two different words a and b that have no letter in common, or 0 if no such pair exists. There are up to 1,000 words of up to 1,000 letters each, so comparing the letters of every pair directly is too slow.
Examples
Input: words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Output: 16
Why: "abcw" and "xtfn" share no letter, and 4 * 4 = 16Input: words = ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Output: 4
Why: "ab" and "cd" is the best disjoint pairInput: words = ["a", "aa", "aaa"]
Output: 0
Why: edge case, every pair shares the letter aHints
0 / 3
Checking whether two words overlap letter by letter costs time proportional to their length, for every one of the n² pairs. Can each word's letters be summarised once?
There are only 26 letters, so the set of letters in a word fits in one integer: bit i is on when letter i appears.
Build a mask for every word. Two words share no letter exactly when mask_a & mask_b == 0, a single operation. Check every pair with that test and keep the best product.
Solution
Each word is turned into a 26-bit mask of the letters it uses, which costs one pass over its letters. Set intersection is then a bitwise AND, so testing a pair is a single operation no matter how long the words are. Keeping only the longest word for each distinct mask can shrink the list further, since words with the same letter set are interchangeable and only the longest matters. Building the masks is O(L) for L total letters, and the pair loop is O(n²) constant-time checks; space is O(n).
def best_disjoint_product(words):
longest = {} # letter mask -> longest word length
for w in words:
mask = 0
for ch in w:
mask |= 1 << (ord(ch) - ord("a")) # add the letter to the set
longest[mask] = max(longest.get(mask, 0), len(w))
items = list(longest.items())
best = 0
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i][0] & items[j][0] == 0: # no letter in common
best = max(best, items[i][1] * items[j][1])
return best
print(best_disjoint_product(["abcw", "baz", "foo", "bar", "xtfn", "abcdef"])) # -> 16
print(best_disjoint_product(["a", "ab", "abc", "d", "cd", "bcd", "abcd"])) # -> 4
print(best_disjoint_product(["a", "aa", "aaa"])) # -> 0Stuck on the idea rather than the code? Bitmask as a Set covers it.