Skip to main content
Talentd

Maximum Length of a Concatenated String with Unique Characters - Solution & Explanation

MediumArrayStringBacktrackingBit Manipulation18 min readAsked at: Microsoft, Meta, Palo Alto Networks +3
Practice this problem

Problem Statement

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 <= 16
  • 1 <= arr[i].length <= 26
  • arr[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.

This C solution uses a recursive helper function to concatenate strings from the array while ensuring all characters are unique, tracked using a count array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n), where n is the number of strings.
Space Complexity: O(n), for the recursive stack and current string.

Try this approach in the editor →

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.

This C solution uses bitwise operations to track character inclusion across the 26 possible letters. Recursion explores concatenation options, using the bitmask for collision detection.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n), similar to previous approaches for evaluating combinations.
Space Complexity: O(n), due to the recursive stack with depth dependent on input size.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Backtracking with String Set

Time Complexity: O(2^n), where n is the number of strings.
Space Complexity: O(n), for the recursive stack and current string.

Bitmasking for Character Uniqueness Check

Time Complexity: O(2^n), similar to previous approaches for evaluating combinations.
Space Complexity: O(n), due to the recursive stack with depth dependent on input size.

State Compression + Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Backtracking with Character SetO(2^n * L)O(n + L)When implementing quickly in interviews or explaining subset exploration logic
Bitmasking for Character UniquenessO(2^n)O(n)When optimizing character checks using bit operations for faster validation

Video Solution

Maximum Length of a Concatenated String with Unique Characters - Leetcode 1239 - Python • NeetCode • 33,930 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Length of a Concatenated String with Unique Characters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays