NeetCode #507LC-1239MediumBacktracking
← Back to All Problems#507 · #1239 · Maximum Length of a Concatenated String with Unique Characters(串联字符串的最大长度)
📌 Problem Statement & Constraints
You are given an array of strings
arr. Concatenate a subsequence of them so that the concatenated string has all unique characters. Return the maximum possible length. Constraints: 1 <= arr.length <= 16, 1 <= arr[i].length <= 26, lowercase letters.💡 Core Algorithmic Approaches
- First discard any string that itself has duplicate characters, since it can never be used.
- Represent each remaining string as a 26-bit mask of its characters.
- Backtrack over the strings, adding one only when its mask does not overlap the accumulated mask.
- The bitmask makes the compatibility test a single AND, and the length is tracked separately.
💻 Benchmark Python3 Implementation
class Solution:
def maxLength(self, arr: List[str]) -> int:
# keep only strings with no internal duplicates, as (mask, length)
opts = []
for w in arr:
m = 0
ok = True
for ch in w:
bit = 1 << (ord(ch) - 97)
if m & bit: # duplicate inside this string
ok = False
break
m |= bit
if ok:
opts.append((m, len(w)))
self.best = 0
def dfs(i: int, mask: int, length: int) -> None:
self.best = max(self.best, length)
for j in range(i, len(opts)):
m, L = opts[j]
if m & mask == 0: # no overlapping characters
dfs(j + 1, mask | m, length + L)
dfs(0, 0, 0)
return self.best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(2^n * n) worst case, with the bitmask making each test O(1).
💾 Space Complexity
O(n) for the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Not filtering strings with internal duplicates: they can never be part of a valid concatenation.
- Comparing strings character by character for overlaps: O(26) per test; the bitmask makes it O(1).
- Updating the best only at the leaves: every partial concatenation is a candidate, so updating at each node is correct and also handles the empty selection.
- Using a set of characters instead of a bitmask: workable, but the bitmask is faster and cleaner.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.