Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.
Return the maximum possible length of s.
Example 1:
Input: arr = ["un","iq","ue"] Output: 4 Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique". Maximum length is 4.
Example 2:
Input: arr = ["cha","r","act","ers"] Output: 6 Explanation: Possible solutions are "chaers" and "acters".
Example 3:
Input: arr = ["abcdefghijklmnopqrstuvwxyz"] Output: 26
Constraints:
1 <= arr.length <= 161 <= arr[i].length <= 26arr[i]contains only lower case English letters.
Solution: Combination + Bit
Time complexity: O(2^n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua class Solution { public: int maxLength(vector<string>& arr) { vector<int> a; for (const string& x : arr) { set<char> s(begin(x), end(x)); if (s.size() != x.length()) continue; a.push_back(0); for (char c : x) a.back() |= 1 << (c - 'a'); } int ans = 0; function<void(int, int)> dfs = [&](int s, int cur) { ans = max(ans, __builtin_popcount(cur)); for (int i = s; i < a.size(); ++i) if ((cur & a[i]) == 0) dfs(i + 1, cur | a[i]); }; dfs(0, 0); return ans; } }; |
Solution 2: DP
Time complexity: O(2^n)
Space complexity: O(2^n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua class Solution { public: int maxLength(vector<string>& arr) { vector<int> a; for (const string& x : arr) { int mask = 0; for (char c : x) mask |= 1 << (c - 'a'); if (__builtin_popcount(mask) != x.length()) continue; a.push_back(mask); } int ans = 0; vector<int> dp{0}; for (int i = 0; i < a.size(); ++i) { int size = dp.size(); for (int j = 0; j < size; ++j) { if (dp[j] & a[i]) continue; int t = dp[j] | a[i]; dp.push_back(t); ans = max(ans, __builtin_popcount(t)); } } return ans; } }; |