Maximum Length of Concatenated String with Unique Characters

Given an array of words, return the length of the longest phrase, containing only unique characters, that you can form by combining the given words together.

Note: A phrase can be formed by concatenating one or more words. All characters in the phrase must be unique (no character appears more than once).

Example(s)

Example 1:

Input: words = ["the","dog","ran"]
Output: 9
Explanation:
You can combine all words: "thedogran" (or "the dog ran" without spaces)
All characters are unique: t, h, e, d, o, g, r, a, n
Length = 9

Example 2:

Input: words = ["the","eagle","flew"]
Output: 4
Explanation:
- "the" has 3 unique characters
- "eagle" has duplicate 'e' (invalid)
- "flew" has 4 unique characters
- "the" + "eagle" has duplicate 'e' (invalid)
- "the" + "flew" has duplicate 'e' (invalid)
- "eagle" + "flew" has duplicate 'e' and 'l' (invalid)
Longest valid phrase: "flew" with length 4

Example 3:

Input: words = ["cha","r","act","ers"]
Output: 6
Explanation:
- "cha" + "r" + "act" = "charact" (has duplicate 'c', invalid)
- "cha" + "r" + "ers" = "charers" (has duplicate 'r', invalid)
- "cha" + "act" = "chaact" (has duplicate 'c' and 'a', invalid)
- "act" + "ers" = "acters" (all unique, length 6) ✓
Longest: "acters" with length 6

Solution

The solution uses backtracking with bit manipulation:

1. Preprocess words: Convert each word to a bitmask and check if it has duplicate characters
2. Backtracking: Try all combinations of words
3. Check uniqueness: Use bitwise operations to check if characters are unique
4. Track maximum: Keep track of the longest valid concatenation

JavaScript Solution

JavaScript Solution - Backtracking with Bit Manipulation

/**
* Find maximum length of concatenated string with unique characters
* @param {string[]} words - Array of words
* @return {number} - Maximum length of valid concatenation
*/
function maxLength(words) {
// Preprocess: convert words to bitmasks and filter invalid words
const validWords = [];
const masks = [];

for (const word of words) {
  let mask = 0;
  let hasDuplicate = false;
  
  // Check for duplicates and build bitmask
  for (const char of word) {
    const bit = 1 << (char.charCodeAt(0) - 'a'.charCodeAt(0));
    
    // If this character is already set, we have a duplicate
    if (mask & bit) {
      hasDuplicate = true;
      break;
    }
    
    mask |= bit;
  }
  
  // Only keep words without duplicate characters
  if (!hasDuplicate) {
    validWords.push(word);
    masks.push(mask);
  }
}

let maxLen = 0;

/**
 * Backtracking function
 * @param {number} index - Current word index
 * @param {number} currentMask - Current character mask
 * @param {number} currentLength - Current concatenation length
 */
function backtrack(index, currentMask, currentLength) {
  // Update maximum
  maxLen = Math.max(maxLen, currentLength);
  
  // Try adding each remaining word
  for (let i = index; i < validWords.length; i++) {
    // Check if this word's characters conflict with current mask
    if ((currentMask & masks[i]) === 0) {
      // No conflict, add this word
      backtrack(i + 1, currentMask | masks[i], currentLength + validWords[i].length);
    }
  }
}

backtrack(0, 0, 0);
return maxLen;
}

// Test cases
console.log('Example 1:', maxLength(["the","dog","ran"])); // 9
console.log('Example 2:', maxLength(["the","eagle","flew"])); // 4
console.log('Example 3:', maxLength(["cha","r","act","ers"])); // 6
console.log('Test 4:', maxLength(["abcdefghijklmnopqrstuvwxyz"])); // 26
console.log('Test 5:', maxLength(["un","iq","ue"])); // 4

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - Backtracking with Bit Manipulation

from typing import List

def max_length(words: List[str]) -> int:
  """
  Find maximum length of concatenated string with unique characters
  
  Args:
      words: List of words
      
  Returns:
      int: Maximum length of valid concatenation
  """
  # Preprocess: convert words to bitmasks and filter invalid words
  valid_words = []
  masks = []
  
  for word in words:
      mask = 0
      has_duplicate = False
      
      # Check for duplicates and build bitmask
      for char in word:
          bit = 1 << (ord(char) - ord('a'))
          
          # If this character is already set, we have a duplicate
          if mask & bit:
              has_duplicate = True
              break
          
          mask |= bit
      
      # Only keep words without duplicate characters
      if not has_duplicate:
          valid_words.append(word)
          masks.append(mask)
  
  max_len = [0]
  
  def backtrack(index: int, current_mask: int, current_length: int):
      """
      Backtracking function
      """
      # Update maximum
      max_len[0] = max(max_len[0], current_length)
      
      # Try adding each remaining word
      for i in range(index, len(valid_words)):
          # Check if this word's characters conflict with current mask
          if (current_mask & masks[i]) == 0:
              # No conflict, add this word
              backtrack(i + 1, current_mask | masks[i], current_length + len(valid_words[i]))
  
  backtrack(0, 0, 0)
  return max_len[0]

# Test cases
print('Example 1:', max_length(["the","dog","ran"]))  # 9
print('Example 2:', max_length(["the","eagle","flew"]))  # 4
print('Example 3:', max_length(["cha","r","act","ers"]))  # 6
print('Test 4:', max_length(["abcdefghijklmnopqrstuvwxyz"]))  # 26
print('Test 5:', max_length(["un","iq","ue"]))  # 4

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Set-Based)

Here's a simpler approach using sets (easier to understand but less efficient):

JavaScript Set-Based

/**
 * Set-based approach (simpler but less efficient)
 */
function maxLengthSet(words) {
  let maxLen = 0;
  
  function backtrack(index, currentChars) {
    // Check if current set is valid (no duplicates)
    if (currentChars.size !== Array.from(currentChars).join('').length) {
      return; // Has duplicates
    }
    
    // Update maximum
    maxLen = Math.max(maxLen, currentChars.size);
    
    // Try adding each remaining word
    for (let i = index; i < words.length; i++) {
      const wordChars = new Set(words[i]);
      
      // Check if word has duplicates internally
      if (wordChars.size !== words[i].length) {
        continue; // Skip words with duplicates
      }
      
      // Check if word conflicts with current characters
      const hasConflict = Array.from(wordChars).some(char => currentChars.has(char));
      
      if (!hasConflict) {
        // No conflict, add this word
        const newChars = new Set([...currentChars, ...wordChars]);
        backtrack(i + 1, newChars);
      }
    }
  }
  
  backtrack(0, new Set());
  return maxLen;
}

Python Set-Based

def max_length_set(words: List[str]) -> int:
    """
    Set-based approach (simpler but less efficient)
    """
    max_len = [0]
    
    def backtrack(index: int, current_chars: set):
        # Check if current set is valid
        if len(current_chars) != sum(len(word) for word in words if all(c in current_chars for c in word)):
            # Simplified check: just verify no duplicates in current set
            pass
        
        # Update maximum
        max_len[0] = max(max_len[0], len(current_chars))
        
        # Try adding each remaining word
        for i in range(index, len(words)):
            word_chars = set(words[i])
            
            # Check if word has duplicates internally
            if len(word_chars) != len(words[i]):
                continue  # Skip words with duplicates
            
            # Check if word conflicts with current characters
            if not word_chars & current_chars:  # No intersection
                # No conflict, add this word
                new_chars = current_chars | word_chars
                backtrack(i + 1, new_chars)
    
    backtrack(0, set())
    return max_len[0]

Complexity

• Time Complexity: O(2^n) in the worst case, where n is the number of valid words. We try all combinations of words. However, pruning (skipping invalid combinations) makes it more efficient in practice.
• Space Complexity: O(n) - For the recursion stack and storing valid words/masks.

Approach

The solution uses backtracking with bit manipulation:

1. Preprocess words:

   • Convert each word to a bitmask (26 bits for 26 letters)
   • Filter out words with duplicate characters
   • Store valid words and their masks

2. Backtracking:

   • Try all combinations of words
   • Use bitwise AND to check for character conflicts
   • If no conflict (mask & wordMask === 0), add the word
   • Update maximum length as we go

3. Bit manipulation:

   • Each character maps to a bit position (a=0, b=1, ..., z=25)
   • Bitmask represents which characters are present
   • Bitwise AND checks for conflicts
   • Bitwise OR combines masks

Key Insights

• Bit manipulation: Efficient way to track character presence
• Backtracking: Try all combinations of words
• Pruning: Skip invalid combinations early
• Preprocessing: Filter words with duplicates first
• Bitwise operations: Fast conflict detection

Step-by-Step Example

Let's trace through Example 1: words = ["the","dog","ran"]

Step 1: Preprocess words
  "the": 
    - Check duplicates: t, h, e (all unique) ✓
    - Mask: 0b... (bits for t, h, e set)
    - Valid word, length = 3
  
  "dog":
    - Check duplicates: d, o, g (all unique) ✓
    - Mask: 0b... (bits for d, o, g set)
    - Valid word, length = 3
  
  "ran":
    - Check duplicates: r, a, n (all unique) ✓
    - Mask: 0b... (bits for r, a, n set)
    - Valid word, length = 3

Step 2: Backtracking
  Start: index=0, mask=0, length=0
  
  Try "the" (index 0):
    mask & "the" mask = 0 (no conflict) ✓
    mask = mask | "the" mask, length = 3
    Recurse: index=1, mask="the", length=3
    
    Try "dog" (index 1):
      "the" mask & "dog" mask = 0 (no conflict) ✓
      mask = "the" | "dog", length = 6
      Recurse: index=2, mask="thedog", length=6
      
      Try "ran" (index 2):
        "thedog" mask & "ran" mask = 0 (no conflict) ✓
        mask = "thedog" | "ran", length = 9
        maxLen = max(0, 9) = 9
  
  maxLen = 9

Result: 9

Visual Representation

Example 1: words = ["the","dog","ran"]

Word masks:
  "the":  t h e
  "dog":  d o g
  "ran":  r a n

Combination tree:
  Start
    ├─ "the" (length 3)
    │   ├─ "the" + "dog" (length 6)
    │   │   └─ "the" + "dog" + "ran" (length 9) ✓
    │   └─ "the" + "ran" (length 6)
    ├─ "dog" (length 3)
    │   └─ "dog" + "ran" (length 6)
    └─ "ran" (length 3)

Maximum: 9

Edge Cases

• All words have duplicates: Return 0 (no valid concatenation)
• Single word: Return its length if it has unique characters
• No valid words: Return 0
• All words can combine: Return sum of all word lengths
• Large alphabet: Works with any characters (a-z)

Important Notes

• Character uniqueness: Each character can appear at most once in the entire phrase
• Word order: Order of words in concatenation doesn't matter for uniqueness
• Internal duplicates: Words with duplicate characters are invalid
• Bit manipulation: Assumes lowercase letters (a-z) for simplicity
• Backtracking: Explores all valid combinations

Optimization: Early Pruning

We can add early pruning optimizations:

// Sort words by length (descending) to try longer words first
validWords.sort((a, b) => b.length - a.length);

// Early termination if remaining words can't improve maxLen
if (currentLength + remainingMaxLength <= maxLen) {
  return; // Can't improve
}

Related Problems

• Longest Substring Without Repeating Characters: Similar uniqueness constraint
• Partition Labels: Different but related string problem
• Word Break: Different concatenation problem
• Generate Parentheses: Different backtracking problem

Takeaways

• Bit manipulation is efficient for character tracking
• Backtracking explores all valid combinations
• Preprocessing filters invalid words early
• Pruning improves performance significantly
• O(2^n) worst case but much better in practice with pruning