Maximize concatenation length with unique chars
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Coding: Maximum-length unique-character string
You are given an array of strings `arr`.
You may choose **any subset** of these strings and concatenate them in any order. The resulting concatenated string must contain **only unique characters** (i.e., no character appears more than once in the final string).
Return the **maximum possible length** of such a concatenated string.
### Notes / constraints
- Strings contain lowercase English letters `a`–`z`.
- You cannot reorder characters *within* a string, but you may choose the order of concatenation by choosing strings in some order.
- If a string contains duplicate characters internally (e.g., `"aa"`), it can never be part of a valid concatenation.
### Example
- Input: `arr = ["un","iq","ue"]`
- Output: `4` (choose `"un" + "iq"` or `"iq" + "ue"`)
Quick Answer: This question evaluates understanding of string manipulation, set-based uniqueness constraints, and combinatorial subset selection for maximizing concatenation length.
Choose a subset of strings whose concatenation has all unique lowercase letters and return the maximum possible length.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (['un','iq','ue'],)
Expected Output: 4
Explanation: Prompt example.
Input: (['cha','r','act','ers'],)
Expected Output: 6
Explanation: Common example.
Input: (['aa','bb'],)
Expected Output: 0
Explanation: Internal duplicates are skipped.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.