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.
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5
6using namespace std;
7
8bool isUnique(string &s) {
9 vector<int> chars(26, 0);
10 for (char c : s) {
11 if (chars[c - 'a']++ > 0) return false;
12 }
13 return true;
14}
15
16void backtrack(vector<string> &arr, string current, int index, int &max_length) {
17 if (!isUnique(current)) return;
18 if (current.size() > max_length) {
19 max_length = current.size();
20 }
21 for (int i = index; i < arr.size(); i++) {
22 backtrack(arr, current + arr[i], i + 1, max_length);
23 }
24}
25
26int maxLength(vector<string> &arr) {
27 int max_length = 0;
28 backtrack(arr, "", 0, max_length);
29 return max_length;
30}
31
32int main() {
33 vector<string> arr = {"un", "iq", "ue"};
34 cout << maxLength(arr) << endl;
35 return 0;
36}This C++ solution leverages backtracking to explore combinations of strings while checking for uniqueness using a vector to track characters.
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.
This C solution uses bitwise operations to track character inclusion across the 26 possible letters. Recursion explores concatenation options, using the bitmask for collision detection.