⚡Flashcard Drill➔
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

  1. First discard any string that itself has duplicate characters, since it can never be used.
  2. Represent each remaining string as a 26-bit mask of its characters.
  3. Backtrack over the strings, adding one only when its mask does not overlap the accumulated mask.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems