Maximum Length of a Word Selection With All Unique Characters
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an array of lowercase strings `words`.
Select a subset of these words (zero or more, chosen in any order) and concatenate them. The selection is **valid** only if the resulting concatenation uses every character **at most once** — that is, no character of the alphabet appears twice across all chosen words combined.
Return the **maximum possible length** of a valid concatenation.
Notes:
- A single word that already contains a repeated character (for example `"abca"`) can never appear in any valid selection, because it alone breaks the all-unique rule.
- The empty selection is always valid and has length `0`, so the answer is at least `0`.
- Order does not matter; only **which** words are chosen affects validity and total length.
### Examples
**Example 1**
```
Input: words = ["un", "iq", "ue"]
Output: 4
```
Explanation: `"un" + "iq" = "uniq"` has all unique characters (length 4). `"iq" + "ue" = "ique"` also has all unique characters (length 4). `"un" + "ue"` shares `'u'`, so it is invalid. The maximum valid length is 4.
**Example 2**
```
Input: words = ["cha", "r", "act", "ers"]
Output: 6
```
Explanation: `"act" + "ers" = "acters"` (length 6) uses all distinct characters. `"cha" + "ers"` also gives 6 distinct characters. No valid selection reaches length 7.
**Example 3**
```
Input: words = ["aa", "bb"]
Output: 0
```
Explanation: Each word contains a repeated character, so no word can be used. The best valid selection is the empty one.
### Constraints
- `1 <= words.length <= 16`
- `1 <= words[i].length <= 26`
- `words[i]` consists only of lowercase English letters `'a'`–`'z'`.
### Output
Return a single integer: the maximum length of a valid (all-unique-character) concatenation of a chosen subset of `words`.
Quick Answer: This question evaluates a candidate's grasp of bitmask representation and subset-based dynamic programming or backtracking. It tests the ability to reason about combinatorial search over small input sizes, a common way interviewers probe algorithmic problem-solving in coding rounds. The task falls under coding and algorithms, requiring practical application of state-space pruning rather than purely theoretical knowledge.
You are given an array of lowercase strings `words`.
Select a subset of these words (zero or more, chosen in any order) and concatenate them. The selection is **valid** only if the resulting concatenation uses every character **at most once** — no character of the alphabet appears twice across all chosen words combined.
Return the **maximum possible length** of a valid concatenation.
Notes:
- A single word that already contains a repeated character (e.g. `"abca"`) can never appear in any valid selection.
- The empty selection is always valid and has length `0`, so the answer is at least `0`.
- Order does not matter; only **which** words are chosen affects validity and total length.
**Example 1**
```
Input: words = ["un", "iq", "ue"]
Output: 4
```
`"un" + "iq" = "uniq"` has all unique characters (length 4). `"un" + "ue"` shares `'u'`, so it is invalid.
**Example 2**
```
Input: words = ["cha", "r", "act", "ers"]
Output: 6
```
`"act" + "ers" = "acters"` (length 6) uses all distinct characters. No valid selection reaches length 7.
**Example 3**
```
Input: words = ["aa", "bb"]
Output: 0
```
Each word contains a repeated character, so no word can be used.
**Constraints**
- `1 <= words.length <= 16`
- `1 <= words[i].length <= 26`
- `words[i]` consists only of lowercase English letters `'a'`-`'z'`.
Constraints
- 1 <= words.length <= 16
- 1 <= words[i].length <= 26
- words[i] consists only of lowercase English letters 'a'-'z'.
Examples
Input: (["un", "iq", "ue"],)
Expected Output: 4
Explanation: "un"+"iq"="uniq" (4 unique chars); "un"+"ue" would share 'u'.
Input: (["cha", "r", "act", "ers"],)
Expected Output: 6
Explanation: "act"+"ers"="acters" uses 6 distinct characters; no selection reaches 7.
Hints
- A word can only be used if its own characters are all distinct. Represent each usable word as a 26-bit mask where bit i means letter i is present; a word with a repeated character has fewer set bits than its length and should be dropped.
- Two words can be combined only when their masks share no bits (mask_a AND mask_b == 0). The combined mask is mask_a OR mask_b, and the combined length is the popcount of that mask.
- With at most 16 words, backtrack over subsets: at each index decide to include a word (if it doesn't conflict with the accumulated mask) or skip it, tracking the best total length seen.