Maximum Length of a Concatenated String with Unique Characters

medium backtracking bitmask

Problem

Given an array of strings, choose a subsequence whose concatenation contains only unique characters. Return the maximum possible length of that concatenation.

Inputarr = ["un","iq","ue"]

Output4

Pick "un"+"iq" (or "iq"+"ue") for length 4. "uniqu" has a duplicate 'u'.

arr (comma-separated)

def max_length(arr):
    masks = []
    for s in arr:
        m = 0
        ok = True
        for ch in s:
            bit = 1 << (ord(ch) - ord('a'))
            if m & bit:
                ok = False; break
            m |= bit
        if ok:
            masks.append(m)
    best = 0
    def dfs(i, cur):
        nonlocal best
        best = max(best, bin(cur).count('1'))
        for j in range(i, len(masks)):
            if cur & masks[j] == 0:
                dfs(j + 1, cur | masks[j])
    dfs(0, 0)
    return best

function maxLength(arr) {
  const masks = [];
  for (const s of arr) {
    let m = 0, ok = true;
    for (const ch of s) {
      const bit = 1 << (ch.charCodeAt(0) - 97);
      if (m & bit) { ok = false; break; }
      m |= bit;
    }
    if (ok) masks.push(m);
  }
  let best = 0;
  const popcount = x => { let n = 0; while (x) { x &= x - 1; n++; } return n; };
  function dfs(i, cur) {
    best = Math.max(best, popcount(cur));
    for (let j = i; j < masks.length; j++) {
      if ((cur & masks[j]) === 0) dfs(j + 1, cur | masks[j]);
    }
  }
  dfs(0, 0);
  return best;
}

class Solution {
    int best = 0;
    public int maxLength(List<String> arr) {
        List<Integer> masks = new ArrayList<>();
        for (String s : arr) {
            int m = 0; boolean ok = true;
            for (char ch : s.toCharArray()) {
                int bit = 1 << (ch - 'a');
                if ((m & bit) != 0) { ok = false; break; }
                m |= bit;
            }
            if (ok) masks.add(m);
        }
        dfs(0, 0, masks);
        return best;
    }
    void dfs(int i, int cur, List<Integer> masks) {
        best = Math.max(best, Integer.bitCount(cur));
        for (int j = i; j < masks.size(); j++) {
            if ((cur & masks.get(j)) == 0) dfs(j + 1, cur | masks.get(j), masks);
        }
    }
}

int best;
void dfs(int i, int cur, vector<int>& masks) {
    best = max(best, __builtin_popcount(cur));
    for (int j = i; j < (int)masks.size(); j++) {
        if ((cur & masks[j]) == 0) dfs(j + 1, cur | masks[j], masks);
    }
}
int maxLength(vector<string>& arr) {
    vector<int> masks;
    for (auto& s : arr) {
        int m = 0; bool ok = true;
        for (char ch : s) {
            int bit = 1 << (ch - 'a');
            if (m & bit) { ok = false; break; }
            m |= bit;
        }
        if (ok) masks.push_back(m);
    }
    best = 0;
    dfs(0, 0, masks);
    return best;
}

Explanation

We want the longest concatenation of chosen words that has no repeated letters. The clever trick is to represent each word as a bitmask: a 26-bit number where bit i is on if the word contains the i-th letter.

With bitmasks, two checks become single operations. A word with an internal duplicate (like "aa") is thrown out while building its mask. To test whether two selections share a letter, we just check cur & masks[j] == 0 — if the AND is zero, they have no letter in common.

The dfs(i, cur) search tries every subset of the remaining words. cur is the combined mask of letters used so far. For each word from index i onward that doesn't conflict, we include it (cur | masks[j]) and recurse. We update best with the number of set bits, which is the current concatenation length.

Example: arr = ["un","iq","ue"]. Combining "un" and "iq" gives no overlap and 4 unique letters; adding "ue" would clash on u, so it is skipped. The best length found is 4.

Counting set bits gives the length instantly, so the search just explores valid combinations and keeps the largest.

Time: O(2^n) Space: O(n)