Maximize Unique Characters from Words
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of lowercase English words. Select a subset of the words such that no character appears more than once across all selected words. In other words, every selected word must have no duplicate letters internally, and any two selected words must have disjoint character sets.
Return the maximum possible number of unique characters covered by a valid subset.
Example:
- Input: `["un", "iq", "ue"]`
- Output: `4`
- Explanation: Select `"un"` and `"iq"` to cover four unique characters.
Clarify edge cases:
- A word containing duplicate letters, such as `"aa"`, cannot be selected.
- The empty subset is allowed and covers `0` characters.
- Assume the alphabet is lowercase English letters unless otherwise specified.
Quick Answer: This question evaluates a candidate's ability to reason about combinatorial constraints and set disjointness while maximizing unique coverage, testing competencies in algorithm design, combinatorics, and constraint-based optimization.
Return the maximum number of unique characters covered by a subset of pairwise-disjoint valid words.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (["un","iq","ue"],)
Expected Output: 4
Explanation: Best score is 4.
Input: (["aa","bc"],)
Expected Output: 2
Explanation: Skip duplicate-letter word.
Input: ([],)
Expected Output: 0
Explanation: Empty subset score is 0.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.