Maximum Length of a Concatenated String With Unique Characters — Medium Problem & Solution

You may pick any subsequence of arr and concatenate the chosen strings. The concatenation is valid only if every character in it is unique.

Difficulty: Medium
Topics: Strings, Bit Manipulation, Backtracking
Asked at: Amazon, Google, Adobe
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You may pick any subsequence of arr and concatenate the chosen strings. The concatenation is valid only if every character in it is unique.

Return the maximum possible length of a valid concatenation. The empty selection is valid and has length 0.

Example 1

Input: arr = ["code","kai","ro"]
Output: 7
Explanation: "code" + "kai" gives 7 distinct characters; "ro" cannot join them because "code" already uses o.

Example 2

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: "un" + "iq" or "iq" + "ue" reach 4; all three repeat u.

Example 3

Input: arr = ["aa","bb"]
Output: 0
Explanation: Each word already repeats a character, so nothing can be used.

Constraints

1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] consists of lowercase English letters.

How to solve Maximum Length of a Concatenated String With Unique Characters

Each usable word is a set of letters, and a valid concatenation is a union of pairwise disjoint sets. Masks turn 'disjoint' into a & b == 0 and 'union' into a | b, so the whole search is bit arithmetic.

Approach

Drop any word that repeats a letter — detect it while building its mask.
Keep a list of reachable masks, starting with just 0.
For each word mask m, extend every reachable mask that does not overlap m and record the new mask.
Track the largest popcount seen; that is the answer.

Why it works

Every subset of compatible words is reachable, because the words are processed in order and each reachable mask records one valid selection from the words seen so far. Popcount equals total length precisely because all letters are distinct.

Complexity

Time — O(2^n) in the worst case, with n at most 16
Space — O(2^n)

Pitfalls

Forgetting to reject self-repeating words lets "aa" contribute a mask of one bit and a length of two.
Extending the reachable list while iterating it re-uses a word twice — collect the new masks first, then append.

Reference solution

Python

from typing import List

def maxLength(arr: List[str]) -> int:
    masks = []
    for w in arr:
        m = 0
        ok = True
        for c in w:
            b = 1 << (ord(c) - 97)
            if m & b:
                ok = False
                break
            m |= b
        if ok:
            masks.append(m)
    seen = [0]
    best = 0
    for m in masks:
        add = []
        for cur in seen:
            if cur & m:
                continue
            nxt = cur | m
            add.append(nxt)
            best = max(best, bin(nxt).count("1"))
        seen.extend(add)
    return best

JavaScript

var maxLength = function(arr) {
    var masks = [];
    for (var t = 0; t < arr.length; t++) {
        var w = arr[t], m = 0, ok = true;
        for (var i = 0; i < w.length; i++) {
            var b = 1 << (w.charCodeAt(i) - 97);
            if ((m & b) !== 0) { ok = false; break; }
            m |= b;
        }
        if (ok) masks.push(m);
    }
    var seen = [0], best = 0;
    for (var k = 0; k < masks.length; k++) {
        var add = [];
        for (var j = 0; j < seen.length; j++) {
            if ((seen[j] & masks[k]) !== 0) continue;
            var next = seen[j] | masks[k];
            add.push(next);
            var bits = 0, x = next;
            while (x > 0) { bits += x & 1; x >>= 1; }
            if (bits > best) best = bits;
        }
        for (var a = 0; a < add.length; a++) seen.push(add[a]);
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue