Count pairs of words with no letters in common

Given a list of lowercase strings, count the unordered pairs of positions (i, j) with i < j whose strings have no character in common. Equal strings at different positions count as different elements.

Interface

Unless you agree on a different interface with the interviewer, assume:

• count_disjoint_pairs(words: list[str]) -> int

Example

count_disjoint_pairs(["abc", "de", "bd", "f", "cab"])  ->  6
# abc-de, abc-f, de-f, de-cab, bd-f, f-cab
count_disjoint_pairs(["ab", "ab", "cd", ""])  ->  5
# ab-cd twice, and the empty string pairs with all three others
count_disjoint_pairs([])  ->  0

Constraints

• Up to 2,000 words, each up to 1,000 lowercase letters.
• An empty string shares nothing with anything, including another empty string.
• The count can exceed 32 bits in larger variants; use 64-bit integers.

Clarifying questions

• Are pairs ordered or unordered, and is a word paired with itself?
• Do duplicates at different positions count separately?
• What does the empty string pair with?
• Is the alphabet only a–z?

What a strong answer covers

• Encoding each word's set of letters as a 26-bit mask, so a pair check is one bitwise AND.
• The direct O(n^2) comparison of masks after O(total length) preprocessing, which is fine at 2,000 words.
• Grouping words by mask and multiplying group counts, so repeated sets are compared once; the special case of mask 0 pairing with itself (c * (c - 1) / 2).
• Tests for duplicates, empty strings and words that share one letter.

Follow-ups

• There are 10^6 words: use the fact that there are at most 2^26 masks, and count pairs with a subset-sum (SOS) DP over the complement mask.
• Return the pair with the largest product of lengths that share no letters.
• The alphabet is all of Unicode.