Java
-
import java.util.*; /** 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 <= 16 1 <= arr[i].length <= 26 arr[i] contains only lower case English letters. */ public class Maximum_Length_of_a_Concatenated_String_with_Unique_Characters { public static void main(String[] args) { Maximum_Length_of_a_Concatenated_String_with_Unique_Characters out = new Maximum_Length_of_a_Concatenated_String_with_Unique_Characters(); Solution s = out.new Solution(); ArrayList<String> input = new ArrayList<>(); // input.add("cha"); // input.add("r"); // input.add("act"); // input.add("ers"); input.add("un"); input.add("iq"); input.add("ue"); // output: 4 // input.add("yy"); // input.add("bkhwmpbiisbldzknpm"); System.out.println(s.maxLength(input)); } class Solution { int result = 0; public int maxLength(List<String> array) { Set<Integer> visitedIndex = new HashSet<>(); dfs("", 0, array, visitedIndex); return result; } private void dfs(String s, int startIndex, List<String> array, Set<Integer> visitedIndex) { System.out.println(s); // System.out.println(startIndex + "\n"); if (isUniquestring(s)) { result = Math.max(result, s.length()); } else { return; } for (int i = startIndex; i < array.size(); i++) { if (!visitedIndex.contains(i) && isUniqueChar(s, array.get(i))) { visitedIndex.add(i); dfs(s + array.get(i), i+1, array, visitedIndex); visitedIndex.remove(i); } } } private boolean isUniqueChar(String s1, String s2) { for (char each: s1.toCharArray()) { if (s2.indexOf(each) >= 0) { return false; } } return true; } private boolean isUniquestring(String s) { int[] charCount = new int[256]; for (char each: s.toCharArray()) { charCount[each]++; if (charCount[each] > 1) { return false; } } return true; } } }
-
// OJ: https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/ // Time: O(2^N) // Space: O(N) class Solution { public: int maxLength(vector<string>& A) { vector<int> v; for (auto &s : A) { int bs = 0, i = 0; for (; i < s.size(); ++i) { int j = s[i] - 'a'; if (bs >> j & 1) break; bs |= 1 << j; } if (i == s.size()) v.push_back(bs); } int ans = 0; for (int m = 1; m < 1 << v.size(); ++m) { int bs = 0, i = 0; for (; i < v.size(); ++i) { if ((m >> i & 1) == 0) continue; if (bs & v[i]) break; bs |= v[i]; } ans = max(ans, __builtin_popcount(bs)); } return ans; } };
-
# 1239. Maximum Length of a Concatenated String with Unique Characters # https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/ class Solution: def maxLength(self, A: List[str]): dp = [set()] for a in A: if len(set(a)) < len(a): continue a = set(a) for b in dp[:]: if a & b: continue dp.append(a | b) return max(len(a) for a in dp) def maxLength(self, arr: List[str]): n = len(arr) res = 0 for i in range(1 << n): tmp = "" for j in range(n): if i >> j & 1: tmp += arr[j] c = Counter(tmp) if all(v == 1 for v in c.values()): res = max(res, len(tmp)) return res