Maximum Length of a Concatenated String with Unique Characters
MediumArrayStringBacktrackingBit Manipulation
Solution
export function maxLength(arr: string[]): number {
const unique: Set<string>[] = [];
for (const word of arr) {
const wordSet = new Set(word);
if (wordSet.size === word.length) {
unique.push(wordSet);
}
}
const concat: Set<string>[] = [new Set()];
for (const u of unique) {
for (const c of concat) {
if (intersect(u, c).size === 0) {
concat.push(union(u, c));
}
}
}
const answer = concat.reduce((prev, curr) => Math.max(prev, curr.size), 0);
return answer;
}
function intersect<T>(set1: Set<T>, set2: Set<T>) {
return new Set([...set1].filter((x) => set2.has(x)));
}
function union<T>(set1: Set<T>, set2: Set<T>) {
return new Set([...set1, ...set2]);
}