Katkat
Back

Choose the Longest Set of Words with No Repeated Characters

MetaSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

Tests bitmask representation, backtracking with pruning, and combinatorial optimization under character-uniqueness constraints.

Problem Statement

You are given an array of strings words, where each string consists solely of lowercase English letters ('a' through 'z').

You want to select a subset of strings from words such that the string formed by concatenating all chosen words contains no duplicate characters (each character appears at most once in the entire concatenation).

Return the maximum possible length of such a concatenation.

Note that:

  • Individual words that contain duplicate characters within themselves can never be part of a valid subset.
  • An empty selection has a length of 0.

Function Signature

def max_unique_concatenation_length(words: list[str]) -> int:
    pass

Input & Output Format

  • Input: A list of strings words.
  • Output: An integer representing the maximum length of a valid concatenation.

Constraints

  • 1 <= len(words) <= 1000
  • 1 <= len(words[i]) <= 26
  • words[i] consists only of lowercase English letters.

Examples

Example 1

Input: words = ["cha", "r", "act", "ers"]
Output: 6
Explanation: Possible valid combinations include "cha" + "ers" (length 6) or "act" + "ers" (length 6). Neither "cha" nor "act" can be combined together because 'c' and 'a' repeat.

Example 2

Input: words = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26
Explanation: The single word contains all 26 unique characters.

Example 3

Input: words = ["aa", "bb"]
Output: 0
Explanation: Both words contain internal duplicate characters, so no valid non-empty subset exists.

Edge Cases

  • Words with duplicate characters within themselves (e.g., "aba") should be filtered out upfront.
  • Duplicate identical words in words (at most one can ever be chosen, and only if it has all unique characters).
  • No word has unique characters, resulting in an output of 0.
  • Large input lists where pruning subsets that cannot beat the current best answer is required to avoid timeouts.

Hints

Hint 1

Filter out any word that has internal duplicate characters, then convert each valid word into a 26-bit integer bitmask and its corresponding character length.

Hint 2

Since the maximum possible length is bounded by 26, you can prune any search path where the current length plus the maximum remaining available characters cannot exceed the best length found so far.

Hint 3

Sort the candidate bitmasks (e.g., by length descending) and use depth-first search with bitwise operations (`mask1 & mask2 == 0`) to quickly check for disjoint character sets.

Follow-up questions

  • How would you return the actual subset of words that achieves the maximum length instead of just the length?
  • If the input alphabet was extended from 26 lowercase English letters to all 128 ASCII characters, how would your approach and complexity change?
  • Suppose each word has an associated positive score (not necessarily equal to its length) and we want to maximize total score. How does this affect branch-and-bound pruning?