Katkat
Back

Select words to maximize unique characters

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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:
  • every character in s is unique (no character repeats), and
  • |s| is maximized among all valid choices.

Examples

  • words = ["un", "iq", "ue"]
  • One optimal answer: "uniq" (length 4). You cannot use all three, because "un" and "ue" both contain u.
  • words = ["aa", "bc", "d"]
  • "aa" cannot be used (it already repeats a), so an optimal answer is "bcd" (length 3).

Clarifying Questions to Ask

  • What is the character domain — guaranteed lowercase English letters only, or can words contain digits, uppercase, punctuation, or Unicode? (This decides whether a 26-bit mask is safe.)
  • How large can words.length and the total character count get? (Determines whether exhaustive subset search is acceptable or whether a smarter prune is required.)
  • Can words contain empty strings or duplicate words, and how should those be treated?
  • If multiple subsets tie for the maximum, is any one acceptable, or is there a tie-break rule (e.g. lexicographically smallest)?
  • Do I need to return the string itself, or just its length / the chosen indices?

Constraints & Assumptions

  • 1 <= words.length <= 16 (small enough that exhaustively considering every subset is on the table; confirm the bound).
  • Total characters across all words is moderate (e.g. <= 200).
  • Characters are lowercase English letters unless stated otherwise — call this assumption out, since the representation depends on it.
  • Any valid maximum-length answer is accepted; concatenation order among chosen words is free.

Hints

Hint 1

What makes a word usable: A word can only ever appear in the answer if it has **no internal duplicate characters** on its own. `"aa"` is invalid before you even combine it with anything. Filter these out first.

Hint 2

Reframing the choice: Concatenation order never changes the *set* of characters produced. So the answer only depends on **which** words you pick — and a valid pick is a group of words whose character sets are **pairwise disjoint**.

Hint 3

Sizing the search: Once a word is reduced to "use it or don't," nothing in between, ask yourself how many distinct ways there are to make that decision across all the words — and whether that count is small enough at the given `words.length` that you can afford to consider every combination. Let the size of that space, plus the disjointness condition from the previous hint, point you at how to organize the exploration and how to represent a word's characters so that checking compatibility against what you've already committed to is cheap.

Follow-up questions

  • How does your representation and runtime change if the alphabet is **not** lowercase letters (digits, uppercase, mixed case, or arbitrary Unicode)? What exactly breaks, and how do you fix it without changing the algorithm?
  • A test harness reports that one **large dataset stalls** under your approach. How would you diagnose whether it's correct-but-slow versus stuck, and what would you tune to make the pruning fire harder?
  • You're handed an existing **scoring/counting helper that returns a wrong number** (no crash). How would you localize the bug with a minimal reproducing input and an oracle?
  • How would you reformulate this as an **iterative subset DP** instead of recursion, and what are the memory trade-offs versus the pruned recursive search?