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
    

All Problems

All Solutions