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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MaxLength(IList<string> arr) {
6 return Backtrack(arr, "", 0);
7 }
8
9 private int Backtrack(IList<string> arr, string current, int index) {
10 if (!IsUnique(current)) return 0;
11 int maxLength = current.Length;
12 for (int i = index; i < arr.Count; i++) {
13 maxLength = Math.Max(maxLength, Backtrack(arr, current + arr[i], i + 1));
14 }
15 return maxLength;
16 }
17
18 private bool IsUnique(string s) {
19 int[] chars = new int[26];
20 foreach (char c in s) {
21 if (chars[c - 'a']++ > 0) return false;
22 }
23 return true;
24 }
25
26 public static void Main() {
27 var arr = new List<string> { "un", "iq", "ue" };
28 var solution = new Solution();
29 Console.WriteLine(solution.MaxLength(arr));
30 }
31}This C# solution uses a recursive approach and employs integer arrays to track character occurrences, similar to C++ and Java implementations.
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.
using System.Collections.Generic;
public class Solution {
public int MaxLength(IList<string> arr) {
return BitmaskHelper(arr, 0, 0);
}
private int BitmaskHelper(IList<string> arr, int index, int bitmask) {
int maxLength = 0;
for (int i = index; i < arr.Count; i++) {
int newBitmask = 0;
bool valid = true;
foreach (char c in arr[i]) {
int mask = 1 << (c - 'a');
if ((bitmask & mask) != 0) {
valid = false;
break;
}
newBitmask |= mask;
}
if (valid) {
maxLength = Math.Max(maxLength, BitmaskHelper(arr, i + 1, bitmask | newBitmask) + arr[i].Length);
}
}
return maxLength;
}
public static void Main() {
var arr = new List<string> { "un", "iq", "ue" };
var solution = new Solution();
Console.WriteLine(solution.MaxLength(arr));
}
}The C# solution employs bitmasking to manage and ensure character uniqueness, using combined bit operations for memory-efficient data tracking.