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.
Java code utilizes bitmasking to handle character collisions efficiently. It performs bit manipulations to identify and ignore recurring characters across concats.