Select words to maximize unique characters

Q: Select words to maximize unique characters

This question evaluates understanding of combinatorial search and string manipulation, specifically the ability to reason about unique-character constraints, subset selection, and set-like representations.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem

You are given an array of strings words. You may choose any subset of these strings and concatenate the chosen strings in any order.

Your goal is to produce a concatenated string that contains the maximum possible number of unique characters, subject to the constraint that no character appears more than once in the concatenation.

Return any valid concatenated string (or equivalently, any subset) that achieves the maximum number of unique characters.

Input

words: string[]

Output

A string s such that:
- all characters in s are unique
- |s| is maximized among all valid choices

Examples

words = ["un","iq","ue"]
- One optimal answer: "uniq" (length 4)
words = ["aa","bc","d"]
- "aa" cannot be used (has duplicate a ), optimal answer could be "bcd"

Constraints (typical interview assumptions)

1 <= words.length <= 16 (or small enough to allow backtracking)
Total characters across all words is moderate (e.g., <= 200)
Characters are lowercase English letters (state assumptions if asked)