# 23.01.2024 [1239. Maximum Length of a Concatenated String with Unique Characters]
Max length subsequence of strings array with unique chars.
23.01.2024
1239. Maximum Length of a Concatenated String with Unique Characters medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/481
Problem TLDR
Max length subsequence of strings array with unique chars.
Intuition
Let’s do a brute-force Depth-First Search and keep track of used chars so far.
Approach
we must exclude all strings with duplicate chars
we can use bit masks, then
mask xor word
must not be equalmask or word
for them not to intersect
Complexity
Time complexity:
O(2n)Space complexity:
O(n)
Code
fun maxLength(arr: List<String>): Int {
val sets = arr.filter { it.toSet().size == it.length }
fun dfs(i: Int, s: Set<Char>): Int = if (i == sets.size) 0
else max(
if (sets[i].any { it in s }) 0 else
sets[i].length + dfs(i + 1, s + sets[i].toSet()),
dfs(i + 1, s)
)
return dfs(0, setOf())
}
pub fn max_length(arr: Vec<String>) -> i32 {
let bits: Vec<i32> = arr.into_iter()
.filter(|s| s.len() == s.chars().collect::<HashSet<_>>().len())
.map(|s| s.bytes().fold(0, |m, c| m | 1 << (c - b'a')))
.collect();
fn dfs(bits: &[i32], i: usize, mask: i32) -> i32 {
if i == bits.len() {
return 0;
}
dfs(bits, i + 1, mask).max(if (bits[i] | mask != bits[i] ^ mask) { 0 } else {
bits[i].count_ones() as i32 + dfs(bits, i + 1, mask | bits[i])
})
}
dfs(&bits, 0, 0)
}