Maximum Character Coverage From Words With No Shared Letters
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a list of words and an alphabet. Choose a subset of the words such that no two chosen words share even one character. The coverage of a choice is the number of distinct alphabet characters that appear in at least one chosen word. Return the largest coverage that any valid choice achieves.
### Function Signature
```python
def max_disjoint_coverage(words: list[str], alphabet: str) -> int:
```
### Rules
- Any subset of `words` may be chosen, including the empty subset, whose coverage is 0.
- Two chosen words conflict if some character appears in both of them. A valid choice contains no conflicting pair.
- Words are taken by position in `words`. If the same word appears twice, the two copies share all of their characters, so at most one copy can be chosen.
- Because no word repeats a character (see Constraints) and chosen words are pairwise disjoint, the coverage of a valid choice equals the total length of the chosen words.
- Return a single integer.
### Constraints
- `1 <= len(alphabet) <= 26`; `alphabet` consists of distinct lowercase English letters, in any order.
- `1 <= len(words) <= 20`
- `1 <= len(words[i]) <= len(alphabet)`
- Every character of every word belongs to `alphabet`, and no character appears more than once within a single word.
### Examples
**Example 1**
```text
Input: words = ["ab", "cd", "bce", "f"], alphabet = "abcdef"
Output: 5
```
`"ab"`, `"cd"` and `"f"` are pairwise disjoint and cover `a`, `b`, `c`, `d` and `f`. The only word containing `e` is `"bce"`, which shares `b` with `"ab"` and `c` with `"cd"`, so any choice that includes it covers at most 4 characters (`"bce"` with `"f"`).
**Example 2**
```text
Input: words = ["abcde", "ab", "cf", "dg", "eh"], alphabet = "abcdefgh"
Output: 8
```
Choosing the longest word `"abcde"` blocks every other word and covers only 5 characters. The four words `"ab"`, `"cf"`, `"dg"` and `"eh"` are pairwise disjoint and together cover all 8 characters.
**Example 3**
```text
Input: words = ["ba", "ab", "c"], alphabet = "cba"
Output: 3
```
`"ba"` and `"ab"` share both of their characters, so at most one of them can be chosen; either one together with `"c"` covers all three characters.
Overview: Given a list of words and an alphabet, choose a subset of words in which no two words share a character, and return the largest number of distinct characters the chosen words can cover together. The problem tests subset search over character sets, conflict pruning, and why simply taking the longest word first can fail.
Read the full Meta Software Engineer interview experience this question came from
You are given a list of strings `words` and a string `alphabet`. Choose a subset of the words such that no two chosen words share even one character. The **coverage** of a choice is the number of distinct `alphabet` characters that appear in at least one chosen word. Return the largest coverage that any valid choice achieves.
Implement `max_disjoint_coverage(words, alphabet)`, which returns a single integer.
### Rules
- Any subset of `words` may be chosen, including the empty subset, whose coverage is 0.
- Two chosen words conflict if some character appears in both of them. A valid choice contains no conflicting pair.
- Words are taken by position in `words`. If the same word appears twice, the two copies share all of their characters, so at most one copy can be chosen.
- Because no word repeats a character and chosen words are pairwise disjoint, the coverage of a valid choice equals the total length of the chosen words.
- The answer is at most `len(alphabet)` (at most 26), so it never exceeds 2^31 - 1; a 32-bit `int` is enough in every language.
### Constraints
- `1 <= len(alphabet) <= 26`; `alphabet` consists of distinct lowercase English letters, in any order.
- `1 <= len(words) <= 20`
- `1 <= len(words[i]) <= len(alphabet)`
- Every character of every word belongs to `alphabet`, and no character appears more than once within a single word.
### Example 1
```text
Input: words = ["ab", "cd", "bce", "f"], alphabet = "abcdef"
Output: 5
```
`"ab"`, `"cd"` and `"f"` are pairwise disjoint and cover `a`, `b`, `c`, `d` and `f`. The only word containing `e` is `"bce"`, which shares `b` with `"ab"` and `c` with `"cd"`, so any choice that includes it covers at most 4 characters (`"bce"` with `"f"`).
### Example 2
```text
Input: words = ["abcde", "ab", "cf", "dg", "eh"], alphabet = "abcdefgh"
Output: 8
```
Choosing the longest word `"abcde"` blocks every other word and covers only 5 characters. The four words `"ab"`, `"cf"`, `"dg"` and `"eh"` are pairwise disjoint and together cover all 8 characters.
Constraints
- 1 <= len(alphabet) <= 26; alphabet consists of distinct lowercase English letters, in any order.
- 1 <= len(words) <= 20
- 1 <= len(words[i]) <= len(alphabet)
- Every character of every word belongs to alphabet, and no character appears more than once within a single word.
Examples
Input: (['a'], 'a')
Expected Output: 1
Explanation: Minimum valid input: one one-letter word over a one-letter alphabet; choosing it covers 1.
Input: (['ab', 'cd', 'bce', 'f'], 'abcdef')
Expected Output: 5
Explanation: Source Example 1: 'ab', 'cd' and 'f' are pairwise disjoint and cover 5; 'bce' conflicts with 'ab' and 'cd', so any choice with it covers at most 4.
Hints
- Because no word repeats a letter and chosen words share no letters, the coverage of a valid choice is just the total length of the chosen words.
- Two words conflict exactly when their letter sets intersect; representing each word's letters compactly makes that test cheap.
- Example 2 shows that taking the longest word first can be wrong; with at most 20 words you can afford to explore choices systematically instead of greedily.