Maximize Letters from Disjoint Words
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an array `words` of lowercase English strings. Choose a subset of words such that:
- each chosen word contains no repeated letter within itself, and
- no letter appears in more than one chosen word.
The score of a subset is the number of distinct letters covered by all chosen words combined. Return the maximum possible score. If multiple subsets achieve the same score, any one of them is acceptable.
Example:
- Input: the 12 month abbreviations such as `jan`, `feb`, ..., `dec`
- The subset `{jan, feb, may}` is **invalid** because the letter `a` appears in both `jan` and `may`.
- A valid answer must use words whose character sets are pairwise disjoint.
Design an efficient algorithm. You may assume all characters come from the 26 lowercase English letters.
Quick Answer: This question evaluates understanding of combinatorial selection, set-based constraints, and efficient representation and enumeration of candidate subsets, measuring competency in handling uniqueness constraints and optimizing an objective over a collection of strings.