Maximum Length of a Concatenated String with Unique Characters solution and explanation
Google
9 more videos on this problem
Maximum Length of a Concatenated String with Unique Characters - Leetcode 1239 - PythonNeetCode · 12:43 · 33K views
Maximum Length of a Concatenated String with Unique Characters | Leetcode 1239 | Live coding sessionCoding Decoded · 12:28 · 5K views
1239 Maximum Length of a Concatenated String with Unique CharactersKelvin Chandra · 6:19 · 5K views
花花酱 LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters - 刷题找工作 EP276Hua Hua · 11:37 · 4K views
LeetCode 1239. Maximum Length of a Concatenated String with Unique CharactersHappy Coding · 23:57 · 4K views
Leetcode - Maximum Length of a Concatenated String with Unique Characters (Python)Timothy H Chang · 6:12 · 1K views
[Tesla Interview] Leetcode 1239. Maximum Length of a Concatenated String with Unique CharactersCode with Carter · 9:49 · 1K views
Leetcode | 1239. Maximum Length of a Concatenated String with Unique Characters | Medium | [Java]Developer Docs · 18:47 · 544 views
Leetcode 1239: Maximum length of a concatenated string with unique chars (Python3)Harper Dada · 37:07 · 462 views
Maximum Length of Concatenated String with Unique Characters SolutionTanishq Chaudhary · 8:25 · 1K views
The problem
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.
Example 1:
Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All the valid concatenations are:
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
Maximum length is 4.
Example 2:
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").
Example 3:
Input: arr = ["abcdefghijklmnopqrstuvwxyz"] Output: 26 Explanation: The only string in arr has all 26 characters.
Constraints:
1 <= arr.length <= 161 <= arr[i].length <= 26arr[i]contains only lowercase English letters.
Approach overview
Problem Overview: You receive an array of strings and need to select any subset whose concatenation contains only unique characters. The goal is to maximize the length of the resulting string. If two chosen strings share a character, that combination becomes invalid.
Approach 1: Recursive Backtracking with Character Set (Time: O(2^n * L), Space: O(n + L))
This approach explores all possible subsets using backtracking. Start with an empty string and recursively decide whether to include each word. Before adding a word, check whether its characters conflict with the current combination using a set or frequency array. If no overlap exists, append the string and continue exploring deeper combinations. The recursion naturally generates all valid subsets, while pruning occurs whenever duplicate characters appear.
Character validation requires iterating through the candidate string and checking membership in a set. If the string itself contains duplicate characters, skip it early. The search tree contains at most 2^n branches, where n is the number of strings. This approach is straightforward and mirrors the subset generation pattern frequently seen in interview problems involving array exploration and string validation.
Approach 2: Bitmasking for Character Uniqueness Check (Time: O(2^n), Space: O(n))
This approach compresses each string into a 26-bit integer mask where each bit represents a lowercase character. If a string contains duplicate characters internally, discard it immediately because its mask would collide with itself. When combining strings, use a bitwise AND operation to check for overlapping characters: maskA & maskB. If the result is zero, the strings share no characters and can be merged using bitwise OR.
Backtracking or iterative subset building works efficiently with these masks. Instead of scanning characters repeatedly, each uniqueness check becomes a constant-time bit operation. This significantly reduces overhead compared to set comparisons. The algorithm maintains a list of valid masks and builds larger combinations while tracking the maximum bit count (string length). Bit manipulation drastically improves constant factors while preserving the same exponential subset exploration.
Recommended for interviews: Start by explaining the recursive backtracking idea because it demonstrates understanding of subset generation and constraint pruning. Then optimize using bit manipulation to represent characters as masks. Interviewers usually expect the bitmask approach because it replaces repeated character scans with constant-time operations and shows deeper familiarity with low-level optimization.
Approach 1: Recursive Backtracking with String Set
This approach uses a recursive backtracking strategy, where we build each possible concatenated string by considering elements one by one. We use a set to track characters for uniqueness and maximize the length only if all characters are unique.
def maxLength(arr):
def is_unique(s):
return len(s) == len(set(s))
def backtrack(current, index):
if not is_unique(current):
return 0
max_length = len(current)
for i in range(index, len(arr)):
max_length = max(max_length, backtrack(current + arr[i], i + 1))
return max_length
return backtrack("", 0)
arr = ["un", "iq", "ue"]
print(maxLength(arr))import java.util.*;
public class MaxLengthConcat {
public static int maxLength(List<String> arr) {
return backtrack(arr, "", 0);
}
private static int backtrack(List<String> arr, String current, int index) {
if (!isUnique(current)) return 0;
int max = current.length();
for (int i = index; i < arr.size(); i++) {
max = Math.max(max, backtrack(arr, current + arr.get(i), i + 1));
}
return max;
}
private static boolean isUnique(String s) {
int[] chars = new int[26];
for (char c : s.toCharArray()) {
if (chars[c - 'a']++ > 0) return false;
}
return true;
}
public static void main(String[] args) {
List<String> arr = Arrays.asList("un", "iq", "ue");
System.out.println(maxLength(arr));
}
}#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
bool isUnique(string &s) {
vector<int> chars(26, 0);
for (char c : s) {
if (chars[c - 'a']++ > 0) return false;
}
return true;
}
void backtrack(vector<string> &arr, string current, int index, int &max_length) {
if (!isUnique(current)) return;
if (current.size() > max_length) {
max_length = current.size();
}
for (int i = index; i < arr.size(); i++) {
backtrack(arr, current + arr[i], i + 1, max_length);
}
}
int maxLength(vector<string> &arr) {
int max_length = 0;
backtrack(arr, "", 0, max_length);
return max_length;
}
int main() {
vector<string> arr = {"un", "iq", "ue"};
cout << maxLength(arr) << endl;
return 0;
}function maxLength(arr) {
function isUnique(s) {
return new Set(s).size === s.length;
}
function backtrack(current, index) {
if (!isUnique(current)) return 0;
let max = current.length;
for (let i = index; i < arr.length; i++) {
max = Math.max(max, backtrack(current + arr[i], i + 1));
}
return max;
}
return backtrack('', 0);
}
const arr = ["un", "iq", "ue"];
console.log(maxLength(arr));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
int maxLengthHelper(char **arr, int index, int size, char *current) {
// Check if current string has all unique characters
int count[26] = {0};
for (int i = 0; current[i] != '\0'; i++) {
if (count[current[i] - 'a']++ > 0) {
return 0;
}
}
// Try every string from the current index onwards
int maxLength = strlen(current);
for (int i = index; i < size; i++) {
char newCurrent[26 * size + 1];
strcpy(newCurrent, current);
strcat(newCurrent, arr[i]);
int length = maxLengthHelper(arr, i + 1, size, newCurrent);
if (length > maxLength) {
maxLength = length;
}
}
return maxLength;
}
int maxLength(char **arr, int arrSize) {
char current[1] = "";
return maxLengthHelper(arr, 0, arrSize, current);
}
int main() {
char *arr[] = {"un", "iq", "ue"};
int size = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", maxLength(arr, size));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxLength(IList<string> arr) {
return Backtrack(arr, "", 0);
}
private int Backtrack(IList<string> arr, string current, int index) {
if (!IsUnique(current)) return 0;
int maxLength = current.Length;
for (int i = index; i < arr.Count; i++) {
maxLength = Math.Max(maxLength, Backtrack(arr, current + arr[i], i + 1));
}
return maxLength;
}
private bool IsUnique(string s) {
int[] chars = new int[26];
foreach (char c in s) {
if (chars[c - 'a']++ > 0) return false;
}
return true;
}
public static void Main() {
var arr = new List<string> { "un", "iq", "ue" };
var solution = new Solution();
Console.WriteLine(solution.MaxLength(arr));
}
}This Python solution employs a recursive backtracking function, evaluating each combination of strings and keeping track of each case's maximum length. Sets are used to ensure uniqueness.
Time Complexity: O(2^n), since all combinations are considered.
Space Complexity: O(n), due to recursion and current string storage.
Approach 2: Bitmasking for Character Uniqueness Check
This approach utilizes bitmasking to efficiently determine if characters are unique when combining strings. Each character is represented by a distinct position in a 32-bit integer, allowing for quick checks and updates.
def maxLength(arr):
def bitmaskHelper(index, bitmask):
max_length = 0
for i in range(index, len(arr)):
new_bitmask = 0
valid = True
for c in arr[i]:
mask = 1 << (ord(c) - ord('a'))
if bitmask & mask:
valid = False
break
new_bitmask |= mask
if valid:
max_length = max(max_length, bitmaskHelper(i + 1, bitmask | new_bitmask) + len(arr[i]))
return max_length
return bitmaskHelper(0, 0)
arr = ["un", "iq", "ue"]
print(maxLength(arr))import java.util.*;
public class MaxLengthConcat {
public static int maxLength(List<String> arr) {
return bitmaskHelper(arr, 0, 0);
}
private static int bitmaskHelper(List<String> arr, int index, int bitmask) {
int maxLength = 0;
for (int i = index; i < arr.size(); i++) {
int newBitmask = 0;
boolean valid = true;
for (char c : arr.get(i).toCharArray()) {
int mask = 1 << (c - 'a');
if ((bitmask & mask) != 0) {
valid = false;
break;
}
newBitmask |= mask;
}
if (valid) {
maxLength = Math.max(maxLength, bitmaskHelper(arr, i + 1, bitmask | newBitmask) + arr.get(i).length());
}
}
return maxLength;
}
public static void main(String[] args) {
List<String> arr = Arrays.asList("un", "iq", "ue");
System.out.println(maxLength(arr));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int bitmaskHelper(vector<string> &arr, int index, int bitmask) {
int maxLength = 0;
for (int i = index; i < arr.size(); i++) {
int newBitmask = 0;
bool valid = true;
for (char c : arr[i]) {
int mask = 1 << (c - 'a');
if (bitmask & mask) {
valid = false;
break;
}
newBitmask |= mask;
}
if (valid) {
maxLength = max(maxLength, bitmaskHelper(arr, i + 1, bitmask | newBitmask) + arr[i].size());
}
}
return maxLength;
}
int maxLength(vector<string> &arr) {
return bitmaskHelper(arr, 0, 0);
}
int main() {
vector<string> arr = {"un", "iq", "ue"};
cout << maxLength(arr) << endl;
return 0;
}function maxLength(arr) {
function bitmaskHelper(index, bitmask) {
let maxLength = 0;
for (let i = index; i < arr.length; i++) {
let newBitmask = 0;
let valid = true;
for (let c of arr[i]) {
let mask = 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
if ((bitmask & mask) !== 0) {
valid = false;
break;
}
newBitmask |= mask;
}
if (valid) {
maxLength = Math.max(maxLength, bitmaskHelper(i + 1, bitmask | newBitmask) + arr[i].length);
}
}
return maxLength;
}
return bitmaskHelper(0, 0);
}
const arr = ["un", "iq", "ue"];
console.log(maxLength(arr));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int bitmaskHelper(char **arr, int index, int arrSize, int bitmask) {
int maxLength = 0;
for (int i = index; i < arrSize; i++) {
int newBitmask = 0;
int valid = 1;
for (char *ch = arr[i]; *ch; ++ch) {
int mask = 1 << (*ch - 'a');
if (bitmask & mask) {
valid = 0;
break;
}
newBitmask |= mask;
}
if (valid) {
maxLength = fmax(maxLength, bitmaskHelper(arr, i + 1, arrSize, bitmask | newBitmask) + strlen(arr[i]));
}
}
return maxLength;
}
int maxLength(char **arr, int arrSize) {
return bitmaskHelper(arr, 0, arrSize, 0);
}
int main() {
char *arr[] = {"un", "iq", "ue"};
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", maxLength(arr, arrSize));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxLength(IList<string> arr) {
return BitmaskHelper(arr, 0, 0);
}
private int BitmaskHelper(IList<string> arr, int index, int bitmask) {
int maxLength = 0;
for (int i = index; i < arr.Count; i++) {
int newBitmask = 0;
bool valid = true;
foreach (char c in arr[i]) {
int mask = 1 << (c - 'a');
if ((bitmask & mask) != 0) {
valid = false;
break;
}
newBitmask |= mask;
}
if (valid) {
maxLength = Math.Max(maxLength, BitmaskHelper(arr, i + 1, bitmask | newBitmask) + arr[i].Length);
}
}
return maxLength;
}
public static void Main() {
var arr = new List<string> { "un", "iq", "ue" };
var solution = new Solution();
Console.WriteLine(solution.MaxLength(arr));
}
}Here, Python employs integer bitmasking for quick checks against character collisions. Recursive calls traverse subsets while tracking valid formations.
Time Complexity: O(2^n), similar to previous approaches due to the possible subsets.
Space Complexity: O(n), for maintaining recursive calls and state information.
Approach 3: State Compression + Bit Manipulation
Since the problem requires that the characters in the subsequence must not be repeated and all characters are lowercase letters, we can use a binary integer of length 26 to represent a subsequence. The i-th bit being 1 indicates that the subsequence contains the i-th character, and 0 indicates that it does not contain the i-th character.
We can use an array s to store the states of all subsequences that meet the conditions. Initially, s contains only one element 0.
Then we traverse the array arr. For each string t, we use an integer x to represent the state of t. Then we traverse the array s. For each state y, if x and y have no common characters, we add the union of x and y to s and update the answer.
Finally, we return the answer.
The time complexity is O(2^n + L), and the space complexity is O(2^n). Here, n is the length of the string array, and L is the sum of the lengths of all strings in the array.
function maxLength(arr: string[]): number {
const s: number[] = [0];
let ans = 0;
for (const t of arr) {
let x = 0;
for (const c of t) {
const b = c.charCodeAt(0) - 97;
if ((x >> b) & 1) {
x = 0;
break;
}
x |= 1 << b;
}
if (x > 0) {
for (let i = s.length - 1; ~i; --i) {
const y = s[i];
if ((x & y) === 0) {
s.push(x | y);
ans = Math.max(ans, bitCount(x | y));
}
}
}
}
return ans;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}func maxLength(arr []string) (ans int) {
s := []int{0}
for _, t := range arr {
x := 0
for _, c := range t {
b := int(c - 'a')
if (x>>b)&1 == 1 {
x = 0
break
}
x |= 1 << b
}
if x > 0 {
for i := len(s) - 1; i >= 0; i-- {
y := s[i]
if (x & y) == 0 {
s = append(s, x|y)
ans = max(ans, bits.OnesCount(uint(x|y)))
}
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Backtracking with String Set | Time Complexity: O(2^n), since all combinations are considered. |
| Bitmasking for Character Uniqueness Check | Time Complexity: O(2^n), similar to previous approaches due to the possible subsets. |
| State Compression + Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking with Character Set | O(2^n * L) | O(n + L) | When implementing quickly in interviews or explaining subset exploration logic |
| Bitmasking for Character Uniqueness | O(2^n) | O(n) | When optimizing character checks using bit operations for faster validation |
Frequently asked questions
Is Maximum Length of a Concatenated String with Unique Characters easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 54%. The challenge comes from combining subset generation with character uniqueness constraints. Understanding backtracking and bitmasking makes the problem much easier to implement efficiently.
Maximum Length of a Concatenated String with Unique Characters Python/Java solution
Python and Java solutions typically use recursive backtracking with either a character set or bitmask. The bitmask version converts strings into integers and uses bitwise AND to detect overlap and bitwise OR to combine masks. This keeps the implementation concise and efficient.
How to solve Maximum Length of a Concatenated String with Unique Characters in O(n)?
An exact O(n) solution does not exist because the problem requires checking combinations of strings. The optimal practical approach is O(2^n) using backtracking with bitmasks, where each subset represents a potential concatenation. Bit operations reduce validation overhead but do not eliminate the exponential subset search.
What is the best approach for Maximum Length of a Concatenated String with Unique Characters?
The most efficient approach uses bitmasking combined with backtracking. Each string is converted into a 26-bit mask representing characters. Bitwise AND quickly checks whether two strings share characters, and bitwise OR merges them. This avoids repeated character scans and keeps the time complexity around O(2^n).
Is Maximum Length of a Concatenated String with Unique Characters asked at Google/Amazon/Meta?
This problem appears frequently in coding interview preparation sets and has patterns similar to questions asked at companies like Amazon, Google, and Meta. It tests subset generation, pruning strategies, and efficient character representation using bit manipulation.
What data structure is used in Maximum Length of a Concatenated String with Unique Characters?
Common implementations use recursion with sets or arrays to track used characters. Optimized solutions replace sets with integer bitmasks where each bit represents a letter from 'a' to 'z'. This allows constant-time uniqueness checks using bitwise operations.
What is the time complexity of Maximum Length of a Concatenated String with Unique Characters?
The time complexity is O(2^n) because the algorithm explores all subsets of the input array. Each subset decision determines whether a string can be appended without creating duplicate characters. With bitmask optimization, character validation becomes constant time.