Longest Concatenation Without Repeated Letters
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Select a subsequence of arr, concatenate its strings in original order, and require every character in the result to be distinct. Return the largest possible result length. Selecting no strings is allowed.
```cpp
class Solution {
public:
int maxLength(vector<string>& arr);
};
```
### Examples
**Example 1:**
```text
Input: arr = ["ab","cd","ac"]
Output: 4
Explanation: ab+cd gives four distinct letters; adding ac to either overlaps a letter.
```
**Example 2:**
```text
Input: arr = ["aa","bc","d"]
Output: 3
Explanation: aa is unusable because it repeats a internally; bc+d gives3.
```
### Constraints
- arr has 1 to 16 strings.
- Each string has length 1 to 26 and contains lowercase English letters only.
### Contract considerations
The answer is a length, independent of which maximum-length subsequence attains it.
```hint Read the boundary condition
Must uniqueness hold only between chosen words, or also within every selected word?
```
### Boundary reminders
The answer is a length, independent of which maximum-length subsequence attains it.
Overview: Longest Concatenation Without Repeated Letters. Select a subsequence of arr, concatenate its strings in original order, and require every character in the result to be distinct.
