Easy Understand | Simple Method | Java | Python ✅
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nUse mask to save all co
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse mask to save all combination in hashmap and use "&" bit manipulation to check if two mask have repeated letter.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O((2^n)^2)$ => $O(4^n)$ \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe worst case is need save every combination, for example the string of length 12 that only contains one kind of letter.\n$O(2^n)$\n\n# Code\nMathod using bit mask\n``` java []\nclass Solution {\n    public int maxProduct(String s) {\n        char[] strArr = s.toCharArray();\n        int n = strArr.length;\n        Map<Integer, Integer> pali = new HashMap<>();\n        // save all elligible combination into hashmap\n        for (int mask = 0; mask < 1<<n; mask++){\n            String subseq = "";\n            for (int i = 0; i < 12; i++){\n                if ((mask & 1<<i) > 0)\n                    subseq += strArr[i];\n            }\n            if (isPalindromic(subseq))\n                pali.put(mask, subseq.length());\n        }\n        // use & opertion between any two combination\n        int res = 0;\n        for (int mask1 : pali.keySet()){\n            for (int mask2 : pali.keySet()){\n                if ((mask1 & mask2) == 0)\n                    res = Math.max(res, pali.get(mask1)*pali.get(mask2));\n            }\n        }\n\n        return res;\n    }\n\n    public boolean isPalindromic(String str){\n        int j = str.length() - 1;\n        char[] strArr = str.toCharArray();\n        for (int i = 0; i < j; i ++){\n            if (strArr[i] != strArr[j])\n                return false;\n            j--;\n        }\n        return true;\n    }\n}\n```\n``` python3 []\nclass Solution:\n    def maxProduct(self, s: str) -> int:\n        n, pali = len(s), {} # bitmask : length\n        for mask in range(1, 1 << n):\n            subseq = ""\n            for i in range(n):\n                if mask & (1 << i):\n                    subseq += s[i]\n            if subseq == subseq[::-1]: # valid is palindromic\n                pali[mask] = len(subseq)\n        res = 0\n        for mask1, length1 in pali.items():\n            for mask2, length2 in pali.items():\n                if mask1 & mask2 == 0: \n                    res = max(res, length1 * length2)\n        return res\n```\n\nThere is another method using recursion\n``` java []\nclass Solution {\n    int res = 0;\n    \n    public int maxProduct(String s) {\n        char[] strArr = s.toCharArray();\n        dfs(strArr, 0, "", "");\n        return res;\n    }\n\n    public void dfs(char[] strArr, int i, String s1, String s2){\n        if(i >= strArr.length){\n            if(isPalindromic(s1) && isPalindromic(s2))\n                res = Math.max(res, s1.length()*s2.length());\n            return;\n        }\n        dfs(strArr, i+1, s1 + strArr[i], s2);\n        dfs(strArr, i+1, s1, s2 + strArr[i]);\n        dfs(strArr, i+1, s1, s2);\n    }\n\n    public boolean isPalindromic(String str){\n        int j = str.length() - 1;\n        char[] strArr = str.toCharArray();\n        for (int i = 0; i < j; i ++){\n            if (strArr[i] != strArr[j])\n                return false;\n            j--;\n        }\n        return true;\n    }\n}\n```\n\n**Please upvate if helpful!!**\n\n![image.png](https://assets.leetcode.com/users/images/4cfe106c-39c2-421d-90ca-53a7797ed7b5_1680845537.3804016.png)
['Bit Manipulation', 'Bitmask', 'Python', 'Java', 'Python3']