Sponsored
Sponsored
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.
1def maxLength(arr):
2 def is_unique(s):
3 return len(s) == len(set(s))
4
5 def backtrack(current, index):
6 if not is_unique(current):
7 return 0
8 max_length = len(current)
9 for i in range(index, len(arr)):
10 max_length = max(max_length, backtrack(current + arr[i], i + 1))
11 return max_length
12
13 return backtrack("", 0)
14
15arr = ["un", "iq", "ue"]
16print(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.
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.
#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;
}This C++ solution follows a similar bitmasking strategy as the C version to efficiently check and manage character uniqueness using bitwise shifts.