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.
- 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 <= 161 <= arr[i].length <= 26arr[i] consists of lowercase English letters.
Hints for Maximum Length of a Concatenated String With Unique Characters
Hint 1
A word with a repeated letter can never be used — filter those out first.
Hint 2
Represent each surviving word as a 26-bit letter mask; two words are compatible when their masks do not overlap.
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
- 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 overlapmand 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 bestJava
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