1239. Maximum Length of a Concatenated String with Unique Characters

Given an array of strings `arr`. String `s` is a concatenation of a sub-sequence of `arr` which have unique characters.

Return the maximum possible length of `s`.

Example 1:

```Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.
```

Example 2:

```Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".
```

Example 3:

```Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26
```

Constraints:

• `1 <= arr.length <= 16`
• `1 <= arr[i].length <= 26`
• `arr[i]` contains only lower case English letters.

1239. Maximum Length of a Concatenated String with Unique Characters
``````struct Solution;

impl Solution {
fn max_length(arr: Vec<String>) -> i32 {
let arr: Vec<u32> = arr
.into_iter()
.filter_map(|s| {
let mut bitset = 0;
for b in s.bytes() {
let bit = 1 << (b - b'a');
if bitset & bit != 0 {
return None;
} else {
bitset |= bit
}
}
Some(bitset)
})
.collect();
let n = arr.len();
let mut res = 0;
Self::dfs(0, 0, &mut res, &arr, n);
res as i32
}

fn dfs(start: usize, cur: u32, max: &mut u32, arr: &[u32], n: usize) {
if start == n {
*max = (*max).max(cur.count_ones());
} else {
if arr[start] & cur == 0 {
Self::dfs(start + 1, cur | arr[start], max, arr, n);
}
Self::dfs(start + 1, cur, max, arr, n);
}
}
}

#[test]
fn test() {
let arr = vec_string!["un", "iq", "ue"];
let res = 4;
assert_eq!(Solution::max_length(arr), res);
let arr = vec_string!["cha", "r", "act", "ers"];
let res = 6;
assert_eq!(Solution::max_length(arr), res);
let arr = vec_string!["abcdefghijklmnopqrstuvwxyz"];
let res = 26;
assert_eq!(Solution::max_length(arr), res);
}
``````