How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Anthropic.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Anthropic during technical interviews.

Maximum-Length Unique-Character Subset | Anthropic Coding Question

Quick Overview

This question evaluates a candidate's ability to combine bitmasking with backtracking or subset enumeration to maximize a constraint over combinations of strings. It tests practical application of state-space search and character-set tracking, a common category in coding interviews assessing algorithmic problem-solving under small input bounds.

Maximum-Length Unique-Character Subset

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Maximum-Length Unique-Character Subset You are given a list of strings. Choose a subset of them and concatenate the chosen strings; the concatenation is **valid** only if every character in it is distinct (no letter appears twice across the whole concatenation). Return the maximum possible length of a valid concatenation. Notes: - Any individual string that already contains a repeated character can never be part of a valid concatenation and must be skipped. - The empty concatenation (choosing nothing) is valid and has length `0`, so the answer is always at least `0`. - Order of concatenation does not matter, since validity depends only on the multiset of characters used. ## Input - `words`: `List[str]`, `1 <= len(words) <= 16`, each string consisting of lowercase English letters, `1 <= len(word) <= 26`. ## Output - An integer: the length of the longest valid concatenation. ## Examples Example 1: ``` words = ["un", "iq", "ue"] => 4 ``` `"un" + "iq" = "uniq"` (length 4) and `"un" + "ue"` share `u`, so 4 is the best. Example 2: ``` words = ["cha", "r", "act", "ers"] => 6 ``` `"act" + "ers"` uses `a,c,t,e,r,s` (all distinct, length 6). Adding any other string repeats a letter, so 6 is the maximum. Example 3: ``` words = ["aa", "bb"] => 0 ``` Each string has an internal duplicate, so nothing can be chosen.

Quick Answer: This question evaluates a candidate's ability to combine bitmasking with backtracking or subset enumeration to maximize a constraint over combinations of strings. It tests practical application of state-space search and character-set tracking, a common category in coding interviews assessing algorithmic problem-solving under small input bounds.

You are given a list of strings. Choose a subset of them and concatenate the chosen strings; the concatenation is **valid** only if every character in it is distinct (no letter appears twice across the whole concatenation). Return the maximum possible length of a valid concatenation. Notes: - Any individual string that already contains a repeated character can never be part of a valid concatenation and must be skipped. - The empty concatenation (choosing nothing) is valid and has length `0`, so the answer is always at least `0`. - Order of concatenation does not matter, since validity depends only on the multiset of characters used. ## Input - `words`: `List[str]`, `1 <= len(words) <= 16`, each string consisting of lowercase English letters, `1 <= len(word) <= 26`. ## Output - An integer: the length of the longest valid concatenation. ## Examples Example 1: ``` words = ["un", "iq", "ue"] => 4 ``` `"un" + "iq" = "uniq"` (length 4) and `"un" + "ue"` share `u`, so 4 is the best. Example 2: ``` words = ["cha", "r", "act", "ers"] => 6 ``` `"act" + "ers"` uses `a,c,t,e,r,s` (all distinct, length 6). Adding any other string repeats a letter, so 6 is the maximum. Example 3: ``` words = ["aa", "bb"] => 0 ``` Each string has an internal duplicate, so nothing can be chosen.

Constraints

1 <= len(words) <= 16
1 <= len(words[i]) <= 26
Each words[i] consists of lowercase English letters ('a'-'z')
The empty selection is valid and yields length 0

Examples

Input: (["un", "iq", "ue"],)

Expected Output: 4

Explanation: "un"+"iq"="uniq" uses u,n,i,q — all distinct, length 4. "un"+"ue" would repeat 'u', so 4 is the maximum.

Input: (["cha", "r", "act", "ers"],)

Expected Output: 6

Explanation: "act"+"ers" uses a,c,t,e,r,s — all distinct, length 6. Adding "cha" or "r" would repeat a letter.

Input: (["aa", "bb"],)

Expected Output: 0

Explanation: Every string has an internal duplicate letter, so none can be selected; the empty concatenation (length 0) is the only valid choice.

Input: (["a"],)

Expected Output: 1

Explanation: A single one-character string is valid on its own, giving length 1.

Input: (["abcdefghijklmnopqrstuvwxyz"],)

Expected Output: 26

Explanation: One string that already uses all 26 distinct letters yields the maximum possible length of 26.

Input: (["abcdefghijklmnopqrstuvwxyz", "abcdefghijklmnopqrstuvwxyz"],)

Expected Output: 26

Explanation: Both strings use every letter, so they conflict with each other; only one can be chosen, giving 26.

Input: (["ab", "cd", "ef"],)

Expected Output: 6

Explanation: All three strings are pairwise disjoint, so all can be concatenated for total length 6.

Input: (["abc", "bcd", "cde"],)

Expected Output: 3

Explanation: Every pair of strings shares at least one letter, so no two can be combined; the best is any single string of length 3.

Hints

Represent each string as a 26-bit bitmask of the letters it uses. A string with an internal duplicate letter can be detected while building its mask (a bit is set twice) — skip those.
Two selections are compatible iff their bitmasks share no bits (mask_a & mask_b == 0). The length of a combined selection is the popcount of the combined mask.
Since n <= 16, enumerate all reachable disjoint combinations: start from {0} and, for each valid word mask, OR it into every existing reachable mask that doesn't conflict. Track the largest popcount seen.

Quick Overview