Maximize Letters from Disjoint Words
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (["un","iq","ue"],)
Expected Output: 4
Explanation: The best score is 4.
Input: (["cha","r","act","ers"],)
Expected Output: 6
Explanation: A maximum disjoint-letter subset covers 6 letters.
Input: (["aa","bb"],)
Expected Output: 0
Explanation: Words with repeated letters are invalid.
Input: ([],)
Expected Output: 0
Explanation: No words covers zero letters.
Hints
- Convert each valid word to a bitmask.
- Backtrack over include/exclude choices while rejecting overlapping masks.