Find Maximum Unique-Character Subset

Problem Description

Given a list of strings, find a subset of these strings such that the total number of unique characters across all strings in the subset is maximized, under the constraint that no two selected strings can share any common characters. Each character is represented by lowercase English letters 'a' through 'z'.

Return the maximum count of unique characters possible by selecting a disjoint subset of the given strings.

Function Signature

def max_unique_characters(strings: List[str]) -> int:

Constraints

• 1 <= len(strings) <= 20
• 1 <= len(strings[i]) <= 26
• All characters are lowercase English letters.

Examples

Example 1: Input: ["abc", "def", "ab"] Output: 6 Explanation: We can choose {"abc", "def"} (unique chars: a, b, c, d, e, f; count 6). We cannot include "ab" because it shares 'a' and 'b' with the first string.

Example 2: Input: ["a", "b", "c", "ab"] Output: 3 Explanation: We can pick any of {a, b, c} to get 3. The string "ab" cannot be combined with "a" or "b".

Edge Cases

• Empty list of strings should return 0.
• Strings that are identical or contained within each other.
• Strings that are inherently self-disjoint (no repeating characters internally).