2 Approaches 🚀 || Full Explained ❤️‍🔥 || [Java/C++/JavaScript/Python]
 Describe your first thoughts on how to solve this problem.  \n\n---\n\n# Approach 1 Brute Force\n1. Initialization:\n    - Initialize an empty list ansList to 
<!-- Describe your first thoughts on how to solve this problem. -->\n\n---\n\n# Approach 1 Brute Force\n1. **Initialization:**\n    - Initialize an empty list `ansList` to store the current valid combinations of strings.\n    - Initialize a variable `ans` to store the maximum length of unique character strings.\n2. **Base case:**\n    - Add an empty string to ansList as the base case.\n    - Iteration over each string in the input list (`arr`):\n3. **For each string str in the input list:**\n    - Check if the string has unique characters using the uniqueCharacterString method.\n    - If the string does not have unique characters, skip to the next iteration.\n    - For each candidate string in ansList, concatenate it with the current string str.\n    - Check if the resulting string has unique characters.\n    - If it does, update the maximum length (ans) and add the new string to a temporary list (currStr).\n4. **Update ansList:**\n    - After processing all strings in the input list, add all strings from currStr to ansList.\n5. **Return the maximum length (ans):**\n    - The final result is the maximum length of a unique character string obtained through concatenation.\n<!-- Describe your approach to solving the problem. -->\n\n# Code\n```Java []\nclass Solution {\n    public int maxLength(List<String> arr) {\n        List<String> ansList = new ArrayList<>();\n        int ans = 0;\n\n        ansList.add("");\n        for(String str : arr) {\n            if(!uniqueCharacterString(str)) {\n                continue;\n            }\n            List<String> currStr = new ArrayList<>();\n\n            for(String candidate : ansList) {\n                String temp = candidate+str;\n                if(uniqueCharacterString(temp)) {\n                    currStr.add(temp);\n                    ans = Math.max(ans, temp.length());\n                }\n            }\n            ansList.addAll(currStr);\n        }\n        return ans;\n    }\n\n    private boolean uniqueCharacterString(String str) {\n        if(str.length() > 26) return false;\n        int[] freq = new int[26];\n\n        for(char ch : str.toCharArray()) {\n            freq[ch-\'a\']++;\n            if(freq[ch-\'a\'] > 1) {\n                return false;\n            }\n        }\n        return true;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int maxLength(vector<string>& arr) {\n        vector<string> ansList = {""};\n        int ans = 0;\n\n        for (const string& str : arr) {\n            if (!uniqueCharacterString(str)) {\n                continue;\n            }\n\n            vector<string> currStr;\n\n            for (const string& candidate : ansList) {\n                string temp = candidate + str;\n                if (uniqueCharacterString(temp)) {\n                    currStr.push_back(temp);\n                    ans = max(ans, static_cast<int>(temp.length()));\n                }\n            }\n\n            ansList.insert(ansList.end(), currStr.begin(), currStr.end());\n        }\n\n        return ans;\n    }\n\nprivate:\n    bool uniqueCharacterString(const string& str) {\n        if (str.length() > 26) return false;\n        int freq[26] = {0};\n\n        for (char ch : str) {\n            freq[ch - \'a\']++;\n            if (freq[ch - \'a\'] > 1) {\n                return false;\n            }\n        }\n        return true;\n    }\n};\n```\n```Python []\nclass Solution:\n    def maxLength(self, arr):\n        ansList = [""]\n        ans = 0\n\n        for string in arr:\n            if not self.uniqueCharacterString(string):\n                continue\n\n            currStr = []\n\n            for candidate in ansList:\n                temp = candidate + string\n                if self.uniqueCharacterString(temp):\n                    currStr.append(temp)\n                    ans = max(ans, len(temp))\n\n            ansList.extend(currStr)\n\n        return ans\n\n    def uniqueCharacterString(self, string):\n        if len(string) > 26:\n            return False\n        freq = [0] * 26\n\n        for ch in string:\n            freq[ord(ch) - ord(\'a\')] += 1\n            if freq[ord(ch) - ord(\'a\')] > 1:\n                return False\n\n        return True\n```\n\n---\n\n# Apporach 2 Bit Manipulation\n\n## *Intution*\n1. **Bit Representation:**\n    - Represent character presence using bit manipulation.\n2. **Efficient Check:**\n    - Use bitwise operations for quick duplicate character checks.\n3. **Iteration:**\n    - Iterate through the string array.\n4. **Bitset Update:**\n    - Update a bitset for each string, checking uniqueness.\n5. **Dynamic Programming:**\n    - Maintain a dynamic programming list (dp) for valid subsequences.\n6. **Reverse Update:**\n    - Update dp in reverse, adding new bitsets based on the current string.\n7. **Max Length:**\n    - Calculate and update the maximum length of unique character concatenations.\n## *Approach*\n1. Initialize `dp` list with a single element `0` (empty string).\n2. For each string s in the input array:\n    - a. Initialize variables a and dup.\n    - b. Iterate through characters in s:\n        - Update dup using bitwise OR to check for duplicate characters.\n        - Update a using bitwise OR to represent the set of characters in s.\n    - c. If dup > 0, continue to the next iteration as s has duplicate characters.\n    - d. Iterate through dp in reverse and update it by adding new bitsets.\n    - e. Update the result by finding the maximum length among valid subsequences.\n# Complexity\n- Time complexity: $$O(N*M)$$ where N is the number of strings in the array and M is the maximum length of a string in the array.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(2^M)$$, where M is the maximum length of a string. The dp list can have up to 2^M elements.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code \n```Java []\nclass Solution {\n    public int maxLength(List<String> arr) {\n        List<Integer> dp = new ArrayList<>();\n        dp.add(0);\n        int res = 0;\n        for (String s : arr) {\n            int a = 0, dup = 0;\n            for (char c : s.toCharArray()) {\n                dup |= a & (1 << (c - \'a\'));\n                a |= 1 << (c - \'a\');\n            }\n            if (dup > 0)    continue;\n            for (int i = dp.size() - 1; i >= 0; i--) {\n                if ((dp.get(i) & a) > 0) continue;\n                dp.add(dp.get(i) | a);\n                res = Math.max(res, Integer.bitCount(dp.get(i) | a));\n            }\n            \n        }\n        return res;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int maxLength(vector<string>& arr) {\n        vector<int> dp = {0};\n        int res = 0;\n        \n        for (const string& s : arr) {\n            int a = 0, dup = 0;\n            for (char c : s) {\n                dup |= a & (1 << (c - \'a\'));\n                a |= 1 << (c - \'a\');\n            }\n            \n            if (dup > 0)\n                continue;\n            \n            for (int i = dp.size() - 1; i >= 0; i--) {\n                if ((dp[i] & a) > 0)\n                    continue;\n                dp.push_back(dp[i] | a);\n                res = max(res, __builtin_popcount(dp[i] | a));\n            }\n        }\n        \n        return res;\n    }\n};\n```\n```Python []\nclass Solution:\n    def maxLength(self, arr: List[str]) -> int:\n        dp = [0]\n        res = 0\n        \n        for s in arr:\n            a, dup = 0, 0\n            for c in s:\n                dup |= a & (1 << (ord(c) - ord(\'a\')))\n                a |= 1 << (ord(c) - ord(\'a\'))\n            \n            if dup > 0:\n                continue\n            \n            for i in range(len(dp) - 1, -1, -1):\n                if (dp[i] & a) > 0:\n                    continue\n                dp.append(dp[i] | a)\n                res = max(res, bin(dp[i] | a).count(\'1\'))\n        \n        return res\n```\n```JavaScript []\nclass Solution:\n    def maxLength(self, arr: List[str]) -> int:\n        dp = [0]\n        res = 0\n        \n        for s in arr:\n            a, dup = 0, 0\n            for c in s:\n                dup |= a & (1 << (ord(c) - ord(\'a\')))\n                a |= 1 << (ord(c) - ord(\'a\'))\n            \n            if dup > 0:\n                continue\n            \n            for i in range(len(dp) - 1, -1, -1):\n                if (dp[i] & a) > 0:\n                    continue\n                dp.append(dp[i] | a)\n                res = max(res, bin(dp[i] | a).count(\'1\'))\n        \n        return res\n```\n\n---\n\n\n---\n\n![5c63d377-8ef4-4beb-b09d-0edb07e09a41_1702955205.6568592.png](https://assets.leetcode.com/users/images/26006df9-b4d9-4694-8cfb-1ff69a336b94_1706030402.3596606.png)\n
['C++', 'Java', 'Python3', 'JavaScript']