Count Pairs of Strings with Disjoint Character Sets
Company: Netflix
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Count Pairs of Strings with Disjoint Character Sets
### Problem
Implement `countDisjointStringPairs(words) -> count`.
Count unordered index pairs `(i, j)` with `i < j` such that `words[i]` and `words[j]` share no character. Two equal strings at different indices are distinct inputs and therefore form their own index pair when the condition holds.
### Portable Contract
- Every word contains only lowercase ASCII letters `a` through `z`.
- `0 <= words.length <= 2,000`.
- The total number of characters across all words is at most `100,000`.
- A word may contain the same letter more than once; only character presence matters for pair compatibility.
- The empty string has no characters and is disjoint from every other string, including another empty string.
- Return the count in a signed 64-bit integer. Under the word-count bound, the maximum possible count is `1,999,000`.
- Do not modify `words`.
- Target `O(T + n^2)` time and `O(n)` auxiliary space, where `n` is the number of words and `T` is their total character count.
```hint Summarize each word once
Repeated copies of a letter inside one word do not affect whether it can pair with another word. Look for a compact summary of the distinct letters that can be reused across pair checks.
```
### Examples
```text
words = ["ab", "cd", "a", "ef"]
count = 5
```
```text
words = ["a", "a", ""]
count = 2
```
### Discussion Requirements
- Explain how the fixed 26-letter alphabet supports a compact per-word representation.
- Derive how two preprocessed representations can be checked for a shared character without rescanning either string.
- Explain why duplicate input strings must still contribute according to their index multiplicity.
- If many words have the same mask, describe how grouping by mask and frequency changes the amount of repeated work without changing the answer.
Quick Answer: Count unordered index pairs of lowercase strings whose character sets do not overlap, treating duplicate strings at different positions separately. Consider exact pair semantics, empty-string behavior, large counts, and efficient comparison across up to two thousand words.
Given a list of lowercase words, count how many unordered index pairs `(i, j)` with `i < j` satisfy: `words[i]` and `words[j]` have no character in common.
Only character *presence* matters. A word may repeat a letter; repeating it changes nothing about which other words it can pair with. Two equal strings sitting at different indices are still two different inputs, so they form their own index pair whenever the condition holds.
The empty string has no characters at all, so it is disjoint from every string -- including another empty string.
Implement `countDisjointStringPairs(words)` and return the number of qualifying index pairs as a single integer.
### Output semantics
Return one integer: the exact number of qualifying `(i, j)` pairs. There is no ordering or tie-breaking to decide -- the answer is a single count, so exactly one value is correct for any input. Return `0` when no pair qualifies. The count is returned in a signed 64-bit integer (`long` in Java, `long long` in C++).
### Example 1
```
Input: words = ["ab", "cd", "a", "ef"]
Output: 5
```
The qualifying pairs are `(ab, cd)`, `(ab, ef)`, `(cd, a)`, `(cd, ef)` and `(a, ef)`. The pair `(ab, a)` is rejected because both contain `a`.
### Example 2
```
Input: words = ["a", "a", ""]
Output: 2
```
The two copies of `"a"` share the letter `a`, so index pair `(0, 1)` does not count. Each of them is disjoint from the empty string at index 2, giving pairs `(0, 2)` and `(1, 2)`.
Constraints
- 0 <= len(words) <= 2000
- Every word contains only lowercase ASCII letters 'a' through 'z'
- 0 <= len(words[i]), and the total number of characters across all words is at most 100000
- The empty string is a valid word and is disjoint from every string, including another empty string
- A word may contain the same letter more than once; only character presence affects pair compatibility
- 0 <= answer <= 1999000, returned in a signed 64-bit integer (Java long, C++ long long)
- words must not be modified
- Target O(T + n^2) time and O(n) auxiliary space, where n = len(words) and T is the total character count
Examples
Input: ([],)
Expected Output: 0
Input: (['abc'],)
Expected Output: 0
Hints
- Rescanning both strings for every pair re-reads the same characters over and over. What is the smallest fact about a word that decides whether it can pair with another word?
- The alphabet is fixed at 26 letters, so 'which letters does this word use' is a fixed-width piece of information no matter how long the word is.
- Two words that use exactly the same set of letters behave identically against every other word. That means words with the same summary can be counted in bulk instead of one at a time -- watch out for how same-summary words pair with each other.