Maximum Length of a Concatenated String with Unique Characters
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores every possible subsequence of the input array arr. For each subsequence, it concatenates the strings and then checks if the resulting string contains only unique characters. The length of each valid concatenated string is compared against a running maximum to find the final answer.
Algorithm
- Initialize a variable
maxLengthto 0. - Generate all
2^npossible subsequences of the input arrayarr, wherenis the number of strings inarr. - This can be done by iterating from
0to2^n - 1and using the binary representation of the loop counter to select which strings to include in the subsequence. - For each subsequence:
- Concatenate all the strings in the subsequence to form a single string
s. - Use a helper function to check if
scontains only unique characters. This is typically done using a frequency array or a hash set. - If
shas unique characters, updatemaxLengthwith the maximum of its current value and the length ofs.
- Concatenate all the strings in the subsequence to form a single string
- After iterating through all subsequences, return
maxLength.
Walkthrough
The core idea is to treat the problem as finding the best subset of strings. Since there are n strings in the input array, there are 2^n possible subsets (or subsequences). We can systematically generate each one. A common way to do this is to loop from 0 to 2^n - 1. Each number in this range can be seen as a bitmask of length n. If the j-th bit is set in the number i, we include the j-th string from arr in our current subsequence. After forming the subsequence, we join its strings and perform a check for character uniqueness. This check involves iterating through the concatenated string and using an auxiliary data structure like a boolean array of size 26 to track seen characters. If the string is valid, we update our maximum length.
import java.util.List; class Solution { public int maxLength(List<String> arr) { int maxLength = 0; int n = arr.size(); // Iterate through all 2^n possible subsequences for (int i = 0; i < (1 << n); i++) { StringBuilder sb = new StringBuilder(); for (int j = 0; j < n; j++) { // Check if the j-th bit is set in i if ((i & (1 << j)) != 0) { sb.append(arr.get(j)); } } String concatenated = sb.toString(); if (hasUniqueCharacters(concatenated)) { maxLength = Math.max(maxLength, concatenated.length()); } } return maxLength; } private boolean hasUniqueCharacters(String s) { if (s.length() > 26) { return false; } int[] freq = new int[26]; for (char c : s.toCharArray()) { if (freq[c - 'a'] > 0) { return false; } freq[c - 'a']++; } return true; }}Complexity
Time
O(2^N * S), where N is the number of strings and S is the total length of strings in a subsequence. In the worst case, this is O(2^N * N * L), where L is the max string length. For each of the 2^N subsequences, we concatenate and then validate the string, which takes time proportional to its length.
Space
O(N * L), where N is the number of strings and L is the maximum length of a string. This space is required to store the longest possible concatenated string.
Trade-offs
Pros
Conceptually simple and straightforward to implement.
Cons
Highly inefficient due to repeated string concatenations and uniqueness checks.
The time complexity makes it infeasible for larger constraints, though it might pass for
N <= 16due to the small problem size.
This approach builds up the set of all possible valid concatenations iteratively. It uses bitmasks to efficiently represent the set of characters in a string, avoiding costly string operations. A list stores the bitmasks of all valid concatenations found so far. For each string in the input array, it tries to combine it with existing valid concatenations, creating new ones if there are no character conflicts.
Algorithm
- Initialize a list,
dp, containing one element:0. This represents the bitmask for an empty string. - Initialize
maxLength = 0. - Iterate through each string
sin the input arrayarr.- First, calculate the bitmask for
s, let's call itsMask. During this calculation, also check ifsitself has duplicate characters. If it does, it cannot be part of any valid concatenation, so we skip it. - Create a temporary list to store new masks generated in this iteration.
- Iterate through each
existingMaskcurrently in thedplist.- Check for character conflicts using a bitwise AND:
(sMask & existingMask) == 0. - If there are no conflicts, a new valid concatenation is possible. Its mask is
newMask = sMask | existingMask. - Add
newMaskto the temporary list. - Update
maxLength = max(maxLength, Integer.bitCount(newMask)).
- Check for character conflicts using a bitwise AND:
- After checking against all existing masks, add all masks from the temporary list to the
dplist.
- First, calculate the bitmask for
- After iterating through all strings,
maxLengthwill hold the answer.
Walkthrough
Instead of generating subsequences and then checking them, we can build the valid results incrementally. We maintain a list of bitmasks, where each mask represents the character set of a valid concatenated string. We start with a list containing just 0 (for an empty string). Then, for each string in the input array, we try to extend every valid result we've found so far.
First, we convert the current string s into a bitmask, but only if s itself contains unique characters. If it does, we iterate through our current list of valid masks. For each existing mask, we check if combining it with the new string's mask would result in a conflict (i.e., a shared character). A bitwise AND operation (&) makes this check extremely fast. If there's no conflict, we create a new mask by combining them with a bitwise OR (|) and add it to our set of results. We keep track of the maximum length (which is the number of set bits in a mask) as we generate new masks.
import java.util.ArrayList;import java.util.List; class Solution { public int maxLength(List<String> arr) { List<Integer> dp = new ArrayList<>(); dp.add(0); // Start with an empty string mask int maxLength = 0; for (String s : arr) { int sMask = 0; int dupCheckMask = 0; for (char c : s.toCharArray()) { // Check for duplicates within the string s itself if ((dupCheckMask & (1 << (c - 'a'))) != 0) { sMask = 0; // Mark as invalid break; } dupCheckMask |= (1 << (c - 'a')); } sMask = dupCheckMask; if (sMask == 0) { continue; // Skip strings with duplicate characters } int currentSize = dp.size(); for (int i = 0; i < currentSize; i++) { int existingMask = dp.get(i); // If no character overlap if ((existingMask & sMask) == 0) { int newMask = existingMask | sMask; dp.add(newMask); maxLength = Math.max(maxLength, Integer.bitCount(newMask)); } } } return maxLength; }}Complexity
Time
O(N * L + 2^N). We spend O(N * L) to preprocess all strings into masks. The main logic involves nested loops where the total number of inner iterations across all outer loops is O(2^N).
Space
O(2^N), where N is the number of strings. The `dp` list can store up to 2^N masks in the worst case.
Trade-offs
Pros
Much more efficient than the naive brute-force by using fast bitwise operations instead of string manipulation.
The logic is iterative, which can be easier to reason about than recursion for some.
Cons
The space complexity is O(2^N), which can be memory-intensive. For N=16, this means storing up to 65,536 integers.
This is a recursive depth-first search (DFS) approach, often called backtracking. It efficiently explores the decision of either including or excluding each string from the final concatenation. The key to its efficiency is using bitmasks to represent character sets, which avoids costly string operations. We also pre-process the input array to filter out strings that contain duplicate characters themselves, as they can never be part of a valid solution.
Algorithm
- Preprocessing:
- Create a list to store the integer bitmasks of strings from
arrthat contain only unique characters. - Iterate through
arr. For each string, calculate its bitmask. If the string has duplicate characters, discard it. Otherwise, add its mask to the list.
- Create a list to store the integer bitmasks of strings from
- Recursion:
- Define a recursive function,
backtrack(index, currentMask).index: The starting index in the list of masks to consider for concatenation.currentMask: The bitmask of the string formed so far.
- Inside
backtrack:- First, update a global
maxLengthwith the number of set bits incurrentMask(Integer.bitCount(currentMask)). - Iterate from
i = indexto the end of the masks list.- Let
nextMaskbe the mask at indexi. - Check for character conflicts:
(currentMask & nextMask) == 0. - If there are no conflicts, it's a valid extension. Make a recursive call to explore this path:
backtrack(i + 1, currentMask | nextMask).
- Let
- First, update a global
- Define a recursive function,
- Initial Call: Start the process by calling
backtrack(0, 0). - Return the final
maxLength.
Walkthrough
This approach models the problem as a state-space search. Each state is defined by the current string we are considering and the set of characters used so far. We use a recursive function to explore this space. The function decides for each string s whether to add it to our current sequence or skip it.
To make this efficient, we first filter the input arr, keeping only strings with unique characters and converting them to integer bitmasks. Then, our recursive function backtrack(index, currentMask) explores the possibilities. At each step, we have a choice: for each subsequent string (from index onwards), we can try to append it. We can only append it if its characters don't overlap with the currentMask. We check this with a fast (currentMask & nextMask) == 0 operation. If they don't overlap, we recurse deeper with an updated mask currentMask | nextMask. We update the maximum length found at every valid state in our search, not just at the leaves of the recursion tree.
import java.util.ArrayList;import java.util.List; class Solution { private int maxLength = 0; public int maxLength(List<String> arr) { List<Integer> uniqueMasks = new ArrayList<>(); for (String s : arr) { int mask = 0; boolean hasDuplicates = false; for (char c : s.toCharArray()) { if ((mask & (1 << (c - 'a'))) != 0) { hasDuplicates = true; break; } mask |= (1 << (c - 'a')); } if (!hasDuplicates) { uniqueMasks.add(mask); } } backtrack(0, 0, uniqueMasks); return maxLength; } private void backtrack(int index, int currentMask, List<Integer> uniqueMasks) { maxLength = Math.max(maxLength, Integer.bitCount(currentMask)); for (int i = index; i < uniqueMasks.size(); i++) { int nextMask = uniqueMasks.get(i); // Check for conflict if ((currentMask & nextMask) == 0) { // Recurse with the new mask backtrack(i + 1, currentMask | nextMask, uniqueMasks); } } }}Complexity
Time
O(N * L + 2^N). O(N * L) for the initial filtering and mask creation. The backtracking function explores at most 2^N states, and each step involves constant-time bitwise operations.
Space
O(N), where N is the number of strings. This space is dominated by the depth of the recursion call stack.
Trade-offs
Pros
Optimal time complexity for this problem's constraints.
Very space-efficient, using only O(N) space for the recursion stack.
A standard and powerful technique for subset/subsequence problems.
Cons
Recursion can lead to a stack overflow for very large N, but given N <= 16, this is not a concern here.
Solutions
Solution
class Solution {public int maxLength(List<String> arr) { int ans = 0; List<Integer> masks = new ArrayList<>(); masks.add(0); for (var s : arr) { int mask = 0; for (int i = 0; i < s.length(); ++i) { int j = s.charAt(i) - 'a'; if (((mask >> j) & 1) == 1) { mask = 0; break; } mask |= 1 << j; } if (mask == 0) { continue; } int n = masks.size(); for (int i = 0; i < n; ++i) { int m = masks.get(i); if ((m & mask) == 0) { masks.add(m | mask); ans = Math.max(ans, Integer.bitCount(m | mask)); } } } return ans; }}class Solution {public: int maxLength(vector<string> &arr) { int ans = 0; vector<int> masks = {0}; for (auto &s : arr) { int mask = 0; for (auto &c : s) { int i = c - 'a'; if (mask >> i & 1) { mask = 0; break; } mask |= 1 << i; } if (mask == 0) { continue; } int n = masks.size(); for (int i = 0; i < n; ++i) { int m = masks[i]; if ((m & mask) == 0) { masks.push_back(m | mask); ans = max(ans, __builtin_popcount(m | mask)); } } } return ans; }};class Solution: def maxLength(self, arr: List[str]) -> int: ans = 0 masks = [0] for s in arr: mask = 0 for c in s: i = ord(c) - ord('a') if mask >> i & 1: mask = 0 break mask |= 1 << i if mask == 0: continue for m in masks: if m & mask == 0: masks . append(m | mask) ans = max(ans, (m | mask). bit_count()) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.