Maximum length of a concatenated string with unique characters

Array String Backtracking Bit Manipulation

54.6% acceptance

Feb 25, 2026

4564

340

You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters. Return the maximum possible length of s. A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_length(arr: Vec<String>) -> i32 {
    // Convert strings to bitmasks (only if no duplicate chars)
    let masks: Vec<(u32, i32)> = arr.iter().filter_map(|s| {
      let mut mask = 0u32;
      let mut len = 0;
      for c in s.bytes() {
        let bit = 1u32 << (c - b'a');
        if mask & bit != 0 { return None; } // duplicate chars
        mask |= bit;
        len += 1;
      }
      Some((mask, len))
    }).collect();

    // DP: set of (mask, length) pairs
    let mut dp: Vec<(u32, i32)> = vec![(0, 0)];
    let mut ans = 0;

    for (mask, len) in masks {
      let prev: Vec<(u32, i32)> = dp.clone();
      for (pmask, plen) in prev {
        if pmask & mask == 0 {
          let nm = pmask | mask;
          let nl = plen + len;
          dp.push((nm, nl));
          ans = ans.max(nl);
        }
      }
    }
    ans
  }
}