✅☑Beats 100% Users || [C++/Java/Python/JavaScript] || 2 Approaches || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n\n---\n\n# Approaches\n(Also explained in the code)\n\n\n### Approach 1\n\n1. maxLength Function:\n\n    - Initializes a 
# PLEASE UPVOTE IF IT HELPED\n\n---\n![Screenshot 2024-01-23 054201.png](https://assets.leetcode.com/users/images/eb18c3a4-dea3-4eeb-a874-5e744f67fba4_1705969019.723713.png)\n\n\n---\n\n# Approaches\n(Also explained in the code)\n\n\n### ***Approach 1***\n\n1. **maxLength Function:**\n\n    - Initializes a variable `maxLength` to keep track of the maximum length of a concatenated string without repeating characters.\n    - Calls the `backTrack` function to explore all possible combinations of strings in the `arr` vector.\n1. **backTrack Function:**\n\n    - Recursively explores combinations of strings starting from the `start` index.\n    - Updates `maxLength` if the length of the current concatenated string is greater than the current `maxLength`.\n    - Calls itself with updated parameters, including the concatenated string and the next starting index.\n1. **isValid Function:**\n\n    - Checks if a new string can be added to the current concatenated string without repeating characters.\n    - Uses an unordered_set `charSet` to keep track of characters in the newString and checks for duplicates.\n    - Also checks if the currentString contains each character from the newString.\n\n\n# Complexity\n- Time complexity:\n   $$O(2^n)$$\n    \n\n- Space complexity:\n   $$O(n)$$\n    \n\n\n# Code\n```C++ []\n\n\nclass Solution {\npublic:\n    int maxLength(vector<string>& arr) {\n        int maxLength = 0;\n        backTrack(arr, "", 0, maxLength);\n        return maxLength;\n    }\n\nprivate:\n    void backTrack(const vector<string>& arr, string current, int start, int& maxLength) {\n        if (maxLength < current.length())\n            maxLength = current.length();\n\n        for (int i = start; i < arr.size(); i++) {\n            if (!isValid(current, arr[i]))\n                continue;\n\n            backTrack(arr, current + arr[i], i + 1, maxLength);\n        }\n    }\n\n    bool isValid(const string& currentString, const string& newString) {\n        unordered_set<char> charSet;\n\n        for (char ch : newString) {\n            if (charSet.count(ch) > 0) {\n                return false; \n            }\n\n            charSet.insert(ch);\n\n            if (currentString.find(ch) != string::npos) {\n                return false;  \n            }\n        }\n\n        return true;\n    }\n};\n\n\n\n\n\n\n```\n```Java []\n\n\npublic class Solution {\n    public int maxLength(List<String> arr) {\n        int[] maxLength = {0};\n        backTrack(arr, "", 0, maxLength);\n        return maxLength[0];\n    }\n\n    private void backTrack(List<String> arr, String current, int start, int[] maxLength) {\n        if (maxLength[0] < current.length())\n            maxLength[0] = current.length();\n\n        for (int i = start; i < arr.size(); i++) {\n            if (!isValid(current, arr.get(i)))\n                continue;\n\n            backTrack(arr, current + arr.get(i), i + 1, maxLength);\n        }\n    }\n\n    private boolean isValid(String currentString, String newString) {\n        Set<Character> charSet = new HashSet<>();\n\n        for (char ch : newString.toCharArray()) {\n            if (charSet.contains(ch)) {\n                return false; \n            }\n\n            charSet.add(ch);\n\n            if (currentString.contains(String.valueOf(ch))) {\n                return false;  \n            }\n        }\n\n        return true;\n    }\n}\n\n\n\n```\n```python3 []\nfrom typing import List\n\nclass Solution:\n    def maxLength(self, arr: List[str]) -> int:\n        maxLength = [0]\n        self.backTrack(arr, "", 0, maxLength)\n        return maxLength[0]\n\n    def backTrack(self, arr, current, start, maxLength):\n        if maxLength[0] < len(current):\n            maxLength[0] = len(current)\n\n        for i in range(start, len(arr)):\n            if not self.isValid(current, arr[i]):\n                continue\n\n            self.backTrack(arr, current + arr[i], i + 1, maxLength)\n\n    def isValid(self, currentString, newString):\n        charSet = set()\n\n        for ch in newString:\n            if ch in charSet:\n                return False\n\n            charSet.add(ch)\n\n            if ch in currentString:\n                return False\n\n        return True\n\n\n\n```\n```javascript []\n\n/**\n * @param {string[]} arr\n * @return {number}\n */\nvar maxLength = function(arr) {\n    let maxLength = [0];\n    backTrack(arr, "", 0, maxLength);\n    return maxLength[0];\n};\n\nfunction backTrack(arr, current, start, maxLength) {\n    if (maxLength[0] < current.length) {\n        maxLength[0] = current.length;\n    }\n\n    for (let i = start; i < arr.length; i++) {\n        if (!isValid(current, arr[i])) {\n            continue;\n        }\n\n        backTrack(arr, current + arr[i], i + 1, maxLength);\n    }\n}\n\nfunction isValid(currentString, newString) {\n    const charSet = new Set();\n\n    for (let ch of newString) {\n        if (charSet.has(ch)) {\n            return false;\n        }\n\n        charSet.add(ch);\n\n        if (currentString.includes(ch)) {\n            return false;\n        }\n    }\n\n    return true;\n}\n\n\n```\n---\n\n\n### ***Approach 2***\n\n1. **Backtracking:**\n\n    - The algorithm uses backtracking to explore different combinations of strings in the `arr` vector.\n    - At each step, it considers whether to include the current string in the combination or skip to the next one.\n1. **Bitmask for Character Presence:**\n\n    - It uses a bitmask (`charSet`) to efficiently track the presence of characters in the current combination.\n    - Each bit in the mask corresponds to a character (\'a\' to \'z\').\n    - If a bit is set (1), it means the corresponding character is present in the combination.\n1. **Validation:**\n\n    - The `isValidString` flag is used to check if the current string can be added to the combination without repeating characters.\n    - It iterates through each character of the current string, updating the bitmask.\n1. **Count Unique Characters:**\n\n    - After processing all strings in the combination, it counts the number of unique characters by counting set bits in the `charSet`.\n\n\n# Complexity\n- Time complexity:\n   $$O(2^n)$$\n    \n\n- Space complexity:\n   $$O(1)$$\n    \n\n\n# Code\n```C++ []\n\n\n\n\nclass Solution {\npublic:\n    int maxLength(vector<string>& arr) {\n        int maxLength = 0;\n        backTrack(arr, 0, 0, maxLength);\n        return maxLength;\n    }\n\nprivate:\n    void backTrack(const vector<string>& arr, int index, int charSet, int& maxLength) {\n        if (index == arr.size()) {\n            int count = 0;\n            for (int i = 0; i < 26; ++i) {\n                if ((charSet & (1 << i)) != 0) {\n                    count++;\n                }\n            }\n            maxLength = max(maxLength, count);\n            return;\n        }\n\n        int newCharSet = charSet;\n        bool isValidString = true;\n\n        for (char ch : arr[index]) {\n            int bit = 1 << (ch - \'a\');\n            if ((newCharSet & bit) == 0) {\n                newCharSet |= bit;\n            } else {\n                isValidString = false;\n                break;\n            }\n        }\n\n        if (isValidString) {\n            backTrack(arr, index + 1, newCharSet, maxLength);\n        }\n\n        backTrack(arr, index + 1, charSet, maxLength);\n    }\n};\n\n\n\n\n\n\n\n\n```\n```Java []\n\n\n\nclass Solution {\n    public int maxLength(List<String> arr) {\n        int maxLength = 0;\n        backTrack(arr, 0, 0, maxLength);\n        return maxLength;\n    }\n\n    private void backTrack(List<String> arr, int index, int charSet, int[] maxLength) {\n        if (index == arr.size()) {\n            int count = 0;\n            for (int i = 0; i < 26; ++i) {\n                if ((charSet & (1 << i)) != 0) {\n                    count++;\n                }\n            }\n            maxLength[0] = Math.max(maxLength[0], count);\n            return;\n        }\n\n        int newCharSet = charSet;\n        boolean isValidString = true;\n\n        for (char ch : arr.get(index).toCharArray()) {\n            int bit = 1 << (ch - \'a\');\n            if ((newCharSet & bit) == 0) {\n                newCharSet |= bit;\n            } else {\n                isValidString = false;\n                break;\n            }\n        }\n\n        if (isValidString) {\n            backTrack(arr, index + 1, newCharSet, maxLength);\n        }\n\n        backTrack(arr, index + 1, charSet, maxLength);\n    }\n}\n\n\n\n\n```\n```python3 []\n\nfrom typing import List\n\nclass Solution:\n    def maxLength(self, arr: List[str]) -> int:\n        maxLength = [0]\n        self.backTrack(arr, 0, 0, maxLength)\n        return maxLength[0]\n\n    def backTrack(self, arr, index, charSet, maxLength):\n        if index == len(arr):\n            count = bin(charSet).count(\'1\')\n            maxLength[0] = max(maxLength[0], count)\n            return\n\n        newCharSet = charSet\n        isValidString = True\n\n        for ch in arr[index]:\n            bit = 1 << (ord(ch) - ord(\'a\'))\n            if newCharSet & bit == 0:\n                newCharSet |= bit\n            else:\n                isValidString = False\n                break\n\n        if isValidString:\n            self.backTrack(arr, index + 1, newCharSet, maxLength)\n\n        self.backTrack(arr, index + 1, charSet, maxLength)\n\n\n\n```\n```javascript []\n/**\n * @param {string[]} arr\n * @return {number}\n */\nvar maxLength = function(arr) {\n    let maxLength = [0];\n    backTrack(arr, 0, 0, maxLength);\n    return maxLength[0];\n};\n\nfunction backTrack(arr, index, charSet, maxLength) {\n    if (index === arr.length) {\n        let count = 0;\n        for (let i = 0; i < 26; ++i) {\n            if ((charSet & (1 << i)) !== 0) {\n                count++;\n            }\n        }\n        maxLength[0] = Math.max(maxLength[0], count);\n        return;\n    }\n\n    let newCharSet = charSet;\n    let isValidString = true;\n\n    for (let ch of arr[index]) {\n        let bit = 1 << (ch.charCodeAt(0) - \'a\'.charCodeAt(0));\n        if ((newCharSet & bit) === 0) {\n            newCharSet |= bit;\n        } else {\n            isValidString = false;\n            break;\n        }\n    }\n\n    if (isValidString) {\n        backTrack(arr, index + 1, newCharSet, maxLength);\n    }\n\n    backTrack(arr, index + 1, charSet, maxLength);\n}\n\n\n\n```\n---\n\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---
['Array', 'String', 'Backtracking', 'Bit Manipulation', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']