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