Katkat
Back

Maximize Letters from Disjoint Words

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use recursion with backtracking and bit manipulation to find the maximum number of unique characters that can be formed by a subset of mutually disjoint words.

Problem Statement

Given a list of strings words, find the maximum total number of unique characters that can be formed by selecting a subset of words, such that no two words in the subset share any common characters.

Two words are considered 'disjoint' if they share zero characters. The objective is to maximize the length of the concatenated string formed by these disjoint words.

Function Signature

def maxUniqueChars(words: List[str]) -> int:

Constraints

  • 1 <= len(words) <= 16
  • 1 <= len(words[i]) <= 26
  • Each word consists of lowercase English letters.

Example 1

Input: words = ["abc", "ade", "efg"] Output: 6 Explanation: We can choose ["abc", "efg"] which are disjoint. Total length = 3 + 3 = 6.

Example 2

Input: words = ["ab", "bc", "cd"] Output: 2 Explanation: Any two words share a character. Max unique length is 2 (e.g., just "ab" or "cd").

Edge Cases

  • Empty input list returns 0.
  • Words with duplicate characters within themselves (e.g., "aba") should be treated as containing the set of unique characters {'a', 'b'}.

Hints

Hint 1

Represent each word as a bitmask of 26 bits, where each bit corresponds to a letter 'a'-'z'.

Hint 2

Pre-process the input to remove words that contain duplicate characters themselves, as they can never be part of a disjoint set.

Hint 3

Use recursion with memoization or backtracking to explore all valid subsets of words, checking for character overlaps using the bitwise AND operator.

Follow-up questions

  • How would the complexity change if the number of words increased to 100 while the average word length remained small?
  • Could this problem be modeled as a Maximum Independent Set problem on a graph? Explain the graph construction.
  • What if we wanted to maximize the number of words chosen rather than the total number of unique characters?