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.To solve #1239 Maximum Length of a Concatenated String with Unique Characters, the key idea is to generate combinations of strings while ensuring that the resulting concatenation contains only unique characters. Since each string can either be included or excluded, the problem naturally fits a backtracking approach.
First, filter out strings that already contain duplicate characters. Then recursively build combinations and check whether adding a new string keeps all characters unique. A common optimization is to represent each string using a bitmask, where each bit corresponds to a character from 'a' to 'z'. This allows quick checks for character overlap using bitwise operations.
During backtracking, maintain the current mask or character set and update the maximum length whenever a valid combination is formed. Bit manipulation significantly reduces comparison overhead and makes conflict detection efficient.
The search space can be large, but pruning invalid combinations early helps keep the exploration manageable.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with Character Set | O(2^n * L) | O(n) |
| Backtracking with Bitmask Optimization | O(2^n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
You can try all combinations and keep mask of characters you have.
You can use DP.
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.
Time Complexity: O(2^n), where n is the number of strings.
Space Complexity: O(n), for the recursive stack and current string.
1function maxLength(arr) {
2 function isUnique(s) {
3 return new Set(s).size === s.length;
4
This JavaScript solution explores subsequences via recursion, checking uniqueness by comparing string lengths with Set sizes, ensuring all characters are distinct.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem can appear in technical interviews at FAANG and other top companies. It tests understanding of backtracking, pruning strategies, and bit manipulation for efficient character conflict detection.
Bitmasks are one of the most efficient representations for this problem because there are only 26 lowercase letters. They allow constant-time checks for overlapping characters and efficient combination using bitwise operations during backtracking.
The optimal approach combines backtracking with bit manipulation. Each string is converted into a bitmask representing its characters, allowing quick overlap checks using bitwise AND operations. This helps efficiently explore valid combinations while pruning invalid ones early.
Backtracking is used because we must explore different combinations of strings to find the maximum valid length. At each step we decide whether to include a string or skip it, while ensuring the concatenated result keeps all characters unique.
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.