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.
1import java.util.*;
2
3public class MaxLengthConcat {
4 public static int maxLength(List<String> arr) {
5 return backtrack(arr, "", 0);
6 }
7
8 private static int backtrack(List<String> arr, String current, int index) {
9 if (!isUnique(current)) return 0;
10 int max = current.length();
11 for (int i = index; i < arr.size(); i++) {
12 max = Math.max(max, backtrack(arr, current + arr.get(i), i + 1));
13 }
14 return max;
15 }
16
17 private static boolean isUnique(String s) {
18 int[] chars = new int[26];
19 for (char c : s.toCharArray()) {
20 if (chars[c - 'a']++ > 0) return false;
21 }
22 return true;
23 }
24
25 public static void main(String[] args) {
26 List<String> arr = Arrays.asList("un", "iq", "ue");
27 System.out.println(maxLength(arr));
28 }
29}This Java solution uses a similar backtracking approach as the C++ example. It checks character uniqueness using an integer array for simplicity.
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.