Katkat
Back

Maximize Unique Characters from Words

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's ability to reason about combinatorial constraints and set disjointness while maximizing unique coverage, testing competencies in algorithm design, combinatorics, and constraint-based optimization.

You are given a list of lowercase English words. Select a subset of the words such that no character appears more than once across all selected words. In other words, every selected word must have no duplicate letters internally, and any two selected words must have disjoint character sets.

Return the maximum possible number of unique characters covered by a valid subset.

Example:

  • Input: ["un", "iq", "ue"]
  • Output: 4
  • Explanation: Select "un" and "iq" to cover four unique characters.

Clarify edge cases:

  • A word containing duplicate letters, such as "aa", cannot be selected.
  • The empty subset is allowed and covers 0 characters.
  • Assume the alphabet is lowercase English letters unless otherwise specified.