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.
Choose a subset of words with no repeated letters internally or across words, returning maximum covered characters.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (['un','iq','ue'],)
Expected Output: 4
Explanation: Classic example.
Input: (['aa','bc'],)
Expected Output: 2
Explanation: Drop invalid word.
Input: (['ab','cd','a'],)
Expected Output: 4
Explanation: Choose disjoint subset.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.