Maximum Length of a Concatenated String With Unique Characters

Medium
642.

Maximum Length of a Concatenated String With Unique Characters

Maximum Length of a Concatenated String With Unique Characters is a medium coding problem on strings, bit manipulation and backtracking, asked in Amazon, Google and Adobe interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} arr
 * @return {number}
 */
var maxLength = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Length of a Concatenated String With Unique Characters

Maximum Length of a Concatenated String With Unique Characters solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Length of a Concatenated String With Unique Characters is a medium coding problem on strings, bit manipulation and backtracking, asked in Amazon, Google and Adobe interviews.

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.

Hints for Maximum Length of a Concatenated String With Unique Characters

  1. Hint 1

    A word with a repeated letter can never be used — filter those out first.

  2. Hint 2

    Represent each surviving word as a 26-bit letter mask; two words are compatible when their masks do not overlap.

  3. Hint 3

    Build up the set of reachable masks one word at a time; the answer is the largest popcount among them.

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

  1. Drop any word that repeats a letter — detect it while building its mask.
  2. Keep a list of reachable masks, starting with just 0.
  3. For each word mask m, extend every reachable mask that does not overlap m and record the new mask.
  4. 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

Java

public static int maxLength(String[] arr) {
    List<Integer> masks = new ArrayList<>();
    for (String w : arr) {
        int m = 0;
        boolean ok = true;
        for (int i = 0; i < w.length(); i++) {
            int b = 1 << (w.charAt(i) - 'a');
            if ((m & b) != 0) { ok = false; break; }
            m |= b;
        }
        if (ok) masks.add(m);
    }
    List<Integer> seen = new ArrayList<>();
    seen.add(0);
    int best = 0;
    for (int m : masks) {
        List<Integer> add = new ArrayList<>();
        for (int cur : seen) {
            if ((cur & m) != 0) continue;
            int next = cur | m;
            add.add(next);
            best = Math.max(best, Integer.bitCount(next));
        }
        seen.addAll(add);
    }
    return best;
}

C++

int maxLength(vector<string>& arr) {
    vector<int> masks;
    for (const string& w : arr) {
        int m = 0;
        bool ok = true;
        for (char c : w) {
            int b = 1 << (c - 'a');
            if (m & b) { ok = false; break; }
            m |= b;
        }
        if (ok) masks.push_back(m);
    }
    vector<int> seen = { 0 };
    int best = 0;
    for (int m : masks) {
        vector<int> add;
        for (int cur : seen) {
            if (cur & m) continue;
            int next = cur | m;
            add.push_back(next);
            best = max(best, __builtin_popcount((unsigned) next));
        }
        for (int v : add) seen.push_back(v);
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Bit Manipulation