Maximize unique characters from a word list
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Maximize Unique Characters From a Word List
You are given a list of strings `words`. You may select **any subset** of these strings (each string used at most once) and concatenate them in any order.
A concatenation is **valid** if **no character appears more than once** in the final concatenated string.
### Task
Return the **maximum possible length** of a valid concatenation.
### Input/Output
- Input: `words: List[str]`
- Output: `int` = maximum valid concatenation length
### Constraints (reasonable interview assumptions)
- `1 <= len(words) <= 20`
- Each word contains only lowercase English letters `a-z`
- `1 <= len(word) <= 26`
### Examples
- `words = ["un","iq","ue"]` → `4` ("uniq" or "ique")
- `words = ["aa","bc"]` → `2` (skip "aa", take "bc")
Quick Answer: This question evaluates algorithmic problem-solving skills focused on combinatorial subset selection and character-uniqueness constraints in strings, within the Coding & Algorithms domain.
Return the maximum length of a concatenation using words with no repeated final character.
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 valid concatenation length is 4.
Input: (["aa","bc"],)
Expected Output: 2
Explanation: Words with duplicate internal letters are skipped.
Input: (["abcdefghijklmnopqrstuvwxyz"],)
Expected Output: 26
Explanation: All letters can be used once.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.