Problem Breakdown
Maximize Unique Characters
Published Feb 16, 2025·
hard
Try This Problem Yourself
Practice in the AI-enabled editor with real-time feedback
You get a list of words and an alphabet. Your job is to pick a subset of words whose combined character coverage is as large as possible, where "combined" means no two picked words are allowed to share even one character.
["abc", "def"] → both, 6 unique chars
["abc", "cde", "fgh"] → abc + fgh, 6 unique chars ("cde" shares "c" with "abc")
["jan","feb",...,"dec"] → best is 12 chars, via the subset feb+mar+jun+oct
["abcdef", "abc", "def"] → either "abcdef" alone or "abc" + "def", tied at 6 charsPattern: Backtracking
Every word is an include-or-skip decision, and you explore those choices by recursing, then undoing, then trying the other branch. Adding a ceiling to cut off hopeless branches is textbook backtracking.
Solution 1, backtracking over include/skip
The natural first frame is a binary decision tree. For each word in the list, you either skip it or include it (as long as its characters don't collide with anything you've already picked). At the bottom of the tree you've either built a legal subset or proved that this sequence of choices doesn't beat what you already have.
Complexity
Where it breaks
Solution 2, pruning with a suffix-union ceiling
The suffix-union ceiling
Sorting by coverage
Complexity
Where it lands
Solution 3, bitmask representation
Words as bitmasks
Complexity
Benchmarks
Takeaways
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium