✅Beats 100% - 2 Approaches - C++/Java/Python/JS - Explained with [ Video ]- DFS and Bit Manipulation
\n\n# YouTube Video Explanation:\n\n **If you want a video for this question please write in the comments** \n\n https://www.youtube.com/watch?v=ujU-jeO1v-k \n\
![Screenshot 2024-01-23 054831.png](https://assets.leetcode.com/users/images/7322b495-e6cd-4483-9dcb-bf6d07415cef_1705969552.6968782.png)\n\n# YouTube Video Explanation:\n\n<!-- **If you want a video for this question please write in the comments** -->\n\n<!-- https://www.youtube.com/watch?v=ujU-jeO1v-k -->\n\nhttps://youtu.be/igAztpYfTOg\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 1600 Subscribers*\n*Current Subscribers: 1557*\n\n---\n\n# Approach 1: Bit Operation\n\n## Intuition:\n1. The idea is to use bit manipulation to represent the presence of characters in a string.\n2. We use an integer to represent a set of characters where each bit corresponds to the presence of a character.\n3. By using bitwise operations, we can efficiently check for duplicate characters in a string.\n4. We iterate through the given array of strings, updating our bitset and checking for uniqueness.\n5. We maintain a dynamic programming list (`dp`) to store the bitsets of valid subsequences.\n\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\n## Complexity Analysis:\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- 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\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# Approach 2: DFS\n\n## Intuition:\n1. The idea is to use Depth-First Search (DFS) to explore all possible combinations of strings in the array.\n2. At each step, we concatenate a string to the existing path and check for uniqueness.\n3. We keep track of the maximum length of valid subsequences during the DFS traversal.\n\n## Approach:\n1. Initialize the result variable to 0.\n2. Define a DFS function that takes the array, current path, and current index as parameters.\n3. In the DFS function:\n   a. Check if the current path has unique characters using a helper function `isUniqueChars`.\n   b. If the path is unique, update the result with the maximum length.\n   c. If the current index is equal to the array size or the path is not unique, return.\n   d. Iterate through the array starting from the current index and make recursive calls to the DFS function.\n4. Call the DFS function with the initial parameters.\n\n## Complexity Analysis:\n- Time Complexity: Exponential, O(2^M), where M is the maximum length of a string in the array. The DFS explores all possible combinations.\n- Space Complexity: O(M), where M is the maximum length of a string. The space is used for the recursive call stack.\n\n## Code\n```Java []\nclass Solution {\n    private int result = 0;\n    public int maxLength(List<String> arr) {\n            if (arr == null || arr.size() == 0)    return 0;\n\n        dfs(arr, "", 0);\n        return result;\n    }\n\n    private void dfs(List<String> arr, String path, int idx) {\n        boolean isUniqueChar = isUniqueChars(path);\n\n        if (isUniqueChar) {\n        result = Math.max(path.length(), result);\n        }\n\n        if (idx == arr.size() || !isUniqueChar) {\n        return;\n        }\n\n        for (int i = idx; i < arr.size(); i++) {\n        dfs(arr, path + arr.get(i), i + 1);\n        }\n\n    }\n\n    private boolean isUniqueChars(String s) {\n        Set<Character> set = new HashSet<>();\n        for (char c : s.toCharArray()) {\n        if (set.contains(c)) {\n            return false;\n        }\n        set.add(c);\n        }\n        return true;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int maxLength(vector<string>& arr) {\n        int result = 0;\n        dfs(arr, "", 0, result);\n        return result;\n    }\n\nprivate:\n    void dfs(const vector<string>& arr, const string& path, int idx, int& result) {\n        if (isUniqueChars(path)) {\n            result = max(result, static_cast<int>(path.length()));\n        }\n\n        if (idx == arr.size() || !isUniqueChars(path)) {\n            return;\n        }\n\n        for (int i = idx; i < arr.size(); i++) {\n            dfs(arr, path + arr[i], i + 1, result);\n        }\n    }\n\n    bool isUniqueChars(const string& s) {\n        unordered_set<char> set;\n        for (char c : s) {\n            if (set.count(c)) {\n                return false;\n            }\n            set.insert(c);\n        }\n        return true;\n    }\n};\n```\n```Python []\nclass Solution:\n    def maxLength(self, arr: List[str]) -> int:\n        result = [0]\n        self.dfs(arr, "", 0, result)\n        return result[0]\n\n    def dfs(self, arr, path, idx, result):\n        if self.isUniqueChars(path):\n            result[0] = max(result[0], len(path))\n\n        if idx == len(arr) or not self.isUniqueChars(path):\n            return\n\n        for i in range(idx, len(arr)):\n            self.dfs(arr, path + arr[i], i + 1, result)\n\n    def isUniqueChars(self, s):\n        char_set = set()\n        for c in s:\n            if c in char_set:\n                return False\n            char_set.add(c)\n        return True\n```\n```Javascript []\n/**\n * @param {string[]} arr\n * @return {number}\n */\nvar maxLength = function(arr) {\n    let result = [0];\n    dfs(arr, "", 0, result);\n    return result[0];\n};\n\nfunction dfs(arr, path, idx, result) {\n    if (isUniqueChars(path)) {\n        result[0] = Math.max(result[0], path.length);\n    }\n\n    if (idx === arr.length || !isUniqueChars(path)) {\n        return;\n    }\n\n    for (let i = idx; i < arr.length; i++) {\n        dfs(arr, path + arr[i], i + 1, result);\n    }\n}\n\nfunction isUniqueChars(s) {\n    let charSet = new Set();\n    for (let c of s) {\n        if (charSet.has(c)) {\n            return false;\n        }\n        charSet.add(c);\n    }\n    return true;\n}\n```\n\n# Conclusion:\n- Both approaches aim to find the maximum length of a concatenated string with unique characters.\n- The bit manipulation approach uses dynamic programming to efficiently store and update valid subsequences.\n- The DFS approach explores all possible combinations of strings to find the maximum length.\n- The bit manipulation approach has a better time complexity but may require more space.\n- The DFS approach has a higher time complexity but consumes less space.\n\n![upvote.png](https://assets.leetcode.com/users/images/3a1239d4-5ecf-48ce-b3f4-7619feb236b0_1705969572.9572623.png)\n\n\n
['Array', 'String', 'Backtracking', 'Bit Manipulation', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']