1239. Maximum Length of a Concatenated String with Unique Characters LeetCode Solution
In this guide, you will get 1239. Maximum Length of a Concatenated String with Unique Characters LeetCode Solution with the best time and space complexity. The solution to Maximum Length of a Concatenated String with Unique Characters problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Length of a Concatenated String with Unique Characters
You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.
Return the maximum possible length of s.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: arr = [“un”,”iq”,”ue”]
Output: 4
Explanation: All the valid concatenations are:
– “”
– “un”
– “iq”
– “ue”
– “uniq” (“un” + “iq”)
– “ique” (“iq” + “ue”)
Maximum length is 4.
Example 2:
Input: arr = [“cha”,”r”,”act”,”ers”]
Output: 6
Explanation: Possible longest valid concatenations are “chaers” (“cha” + “ers”) and “acters” (“act” + “ers”).
Example 3:
Input: arr = [“abcdefghijklmnopqrstuvwxyz”]
Output: 26
Explanation: The only string in arr has all 26 characters.
1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] contains only lowercase English letters.
Complexity Analysis
Time Complexity: O(2^n)
Space Complexity: O(n)
1239. Maximum Length of a Concatenated String with Unique Characters LeetCode Solution in C++
class Solution {
public:
int maxLength(vector<string>& arr) {
vector<int> masks;
for (const string& s : arr) {
const int mask = getMask(s);
if (mask != -1)
masks.push_back(mask);
}
return dfs(masks, 0, /*used=*/0);
}
private:
int dfs(const vector<int>& masks, int s, unsigned used) {
int res = popcount(used);
for (int i = s; i < masks.size(); ++i)
if ((used & masks[i]) == 0)
res = max(res, dfs(masks, i + 1, used | masks[i]));
return res;
}
int getMask(const string& s) {
int mask = 0;
for (const char c : s) {
const int i = c - 'a';
if ((mask & (1 << i)) != 0)
return -1;
mask |= 1 << i;
}
return mask;
}
}; /* code provided by PROGIEZ */
1239. Maximum Length of a Concatenated String with Unique Characters LeetCode Solution in Java
class Solution {
public:
int maxLength(vector<string>& arr) {
vector<bitset<26>> masks;
for (const string& s : arr) {
const bitset<26> mask = getMask(s);
if (mask.contains() == s.length())
masks.push_back(mask);
}
return dfs(masks, 0, /*used=*/bitset<26>());
}
private:
int dfs(const vector<bitset<26>>& masks, int s, bitset<26> used) {
int res = used.contains();
for (int i = s; i < masks.size(); ++i)
if (!(used & masks[i]).any())
res = max(res, dfs(masks, i + 1, used | masks[i]));
return res;
}
bitset<26> getMask(const string& s) {
bitset<26> mask;
for (const char c : s)
mask.set(c - 'a');
return mask;
}
}; // code provided by PROGIEZ
1239. Maximum Length of a Concatenated String with Unique Characters LeetCode Solution in Python
class Solution {
public:
int maxLength(vector<string>& arr) {
vector<unsigned> masks;
for (const string& s : arr) {
const int mask = getMask(s);
if (mask != -1)
masks.push_back(mask);
}
return dfs(masks, 0, /*used=*/0);
}
private:
int dfs(const vector<unsigned>& masks, int i, int used) {
if (i == masks.size())
return 0;
const int pick =
(masks[i] & used) == 0
? popcount(masks[i]) + dfs(masks, i + 1, used | masks[i])
: 0;
const int skip = dfs(masks, i + 1, used);
return max(pick, skip);
}
int getMask(const string& s) {
int mask = 0;
for (const char c : s) {
const int i = c - 'a';
if ((mask & (1 << i)) != 0)
return -1;
mask |= 1 << i;
}
return mask;
}
}; # code by PROGIEZ
