Maximize Unique Letters
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a list of lowercase words, choose any subset of words such that:
- no selected word contains a repeated character internally, and
- no character appears in more than one selected word across the subset.
Return the maximum possible number of distinct characters covered by the selected subset.
Follow-up stages:
1. Solve the exact problem for small inputs such as `n <= 12`.
2. Scale the solution to much larger inputs, potentially up to around `10^4` words. You should preprocess each word into a 26-bit mask, discard words that are internally invalid, and describe or implement pruning and a more scalable state-compression strategy.
Quick Answer: This question evaluates proficiency in combinatorial optimization, bit manipulation, and state-compression techniques for selecting subsets under uniqueness constraints.