Count Pairs of Strings with Disjoint Character Sets

Count Pairs of Strings with Disjoint Character Sets

Given an array of strings words containing lowercase English letters, count the number of unordered index pairs (i, j) such that 0 <= i < j < len(words) and the strings words[i] and words[j] share no common characters (i.e., their character sets are disjoint).

If two identical strings appear at distinct indices, they must be treated as separate elements. An empty string contains no characters, so its character set is disjoint from every other string's character set (including another empty string).

Function Signature

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

Examples

Example 1:

Input: words = ["abc", "def", "bcd", "xyz"]
Output: 4
Explanation:
The disjoint pairs are:
- ("abc", "def") at indices (0, 1)
- ("abc", "xyz") at indices (0, 3)
- ("def", "bcd") at indices (1, 2)
- ("bcd", "xyz") at indices (2, 3)
Pair ("def", "xyz") shares no letters, but let's check: 'd', 'e', 'f' vs 'x', 'y', 'z' -> actually disjoint! That would make 5.
Wait, let's trace carefully: 
Pairs:
(0, 1): "abc" & "def" -> disjoint
(0, 2): "abc" & "bcd" -> share 'b', 'c'
(0, 3): "abc" & "xyz" -> disjoint
(1, 2): "def" & "bcd" -> share 'd'
(1, 3): "def" & "xyz" -> disjoint
(2, 3): "bcd" & "xyz" -> disjoint
Total disjoint pairs = 4: (0, 1), (0, 3), (1, 3), (2, 3).

Example 2:

Input: words = ["a", "", "b", "a"]
Output: 5
Explanation:
Pairs:
- (0, 1): "a" and "" -> disjoint
- (0, 2): "a" and "b" -> disjoint
- (0, 3): "a" and "a" -> share 'a' (not disjoint)
- (1, 2): "" and "b" -> disjoint
- (1, 3): "" and "a" -> disjoint
- (2, 3): "b" and "a" -> disjoint
Total: 5 pairs.

Constraints

• 1 <= len(words) <= 2,000
• 0 <= len(words[i]) <= 1,000
• words[i] consists only of lowercase English letters ('a' - 'z').