[Java] DP with clear explanation - O(n*2^n) beats 89%
Intuition\nThere are multiple ways to approach this problem:\n1. Find all subsequences, then for any 2, check if they overlap, get get product. Time complexity 
# Intuition\nThere are multiple ways to approach this problem:\n1. Find all subsequences, then for any 2, check if they overlap, get get product. Time complexity O(2^n * 2^n * n) = O(n * 4^n).\n2. Divide s to 2 subsequences - for each character, either assign to seq1, or seq2, or discard. now for seq1 and seq2 check if they are palindrome and get product. Time complexity O(n * 3^n). We have 3^n because each character can be in seq1, seq2, or discarded.\n3. Go through all 2^n subsequences. Everytime, for the remaining unpicked characters, treat them as string, then apply DP solution in LC516 "Longest Palindromic Subsequence". Time complexity is O(n^2 * 2^n).\n4. Consolidate solving "Longest Palindromic Subsequence" of all 2^n subsequences together using DP (as a preprocessing). Then from this result we can easily get max product. Time complexity is O(n * 2^n). See details below.\n\n# Approach\nFor all 2^n subsequences, calculate the longest palindromic subsequence of each.\n\nThis can be done with dynamic programming. For example, for s = "leetcode", for sequence 01100101, i.e. "eeoe", we have **recursive relationship**:\n```\npalSubSeq(01100101) = max{\n    2 + palSubSeq(00100100),\n    palSubSeq(00100101),\n    palSubSeq(01100100),\n}\n```\n\nAfter we have palSubSeq[] for all 2^n subsequences, we can calculate max product in this way: go through all seq1 (from 0000000 to 1111111), note its flip-sequence is seq2 = 2^n - 1 - seq1. So product is `palSubSeq[seq1] * palSubSeq[2^n - 1 - seq1]`\n\nCoding-wise, mean challenge is to calculate the DP table palSubSeq[]. We use recursion + memoization here. First we use backtrack to get to all 2^n subsequences. Then for each subsequence, we apply the recursive relationship, and use memoization to avoid duplicate calculation.\n\n# Complexity\n- Time complexity: `O(n * 2^n)`\n\n- Space complexity: `O(2^n)`\n\n# Code\n```\nclass Solution {\n    public int maxProduct(String s) {\n        // 2^n total possible subsequences\n        // first calculate longest palindrome subseq for each possible subsequence\n        // then calculate product\n\n        int length = s.length();    // this is n\n        int count = (int)(Math.pow(2, length)); // this is 2^n\n\n        // the memoization table to store longest palindrome subseq, of all possible subseq\n        // for example, for s="leetcode", palSubSeq[00001011] stores the longest palindrome subseq of sequence "cde"\n        // because there are totally 2^n possible subsequences, the table size is 2^n (note n<=12 so this size <= 4096)\n        int[] palSubSeq = new int[count];\n        // base case: single characters\n        for (int bitIndex = 1; bitIndex < count; bitIndex *= 2) {\n            palSubSeq[bitIndex] = 1;\n        }\n\n        // use bitmask to do backtracking\n        boolean[] bitmask = new boolean[length];\n        for (int i = 0; i < length; i++) {\n            bitmask[i] = false;\n        }\n        // calculate the palSubSeq[] table\n        palSubSeqBacktrack(s, bitmask, 0, palSubSeq);\n\n        // get max product using palSubSeq[]\n        // for any subsequence mask, its flip is 2^n - 1 - mask\n        // for example, 00001011\'s flip is 11110100\n        int maxProduct = 0;\n        for (int i = 0; i < count / 2; i++) {\n            int product = palSubSeq[i] * palSubSeq[count - i - 1];\n            if (product > maxProduct) {\n                maxProduct = product;\n            }\n        }\n        return maxProduct;\n    }\n\n    // 2 stages of recursion calls\n    // stage 1. use backtracking just to get to all 2^n subsequences\n    private static void palSubSeqBacktrack(String s, boolean[] bitmask, int processingIndex, int[] palSubSeq) {\n        if (processingIndex < bitmask.length) {\n            // backtrack to bottom\n            bitmask[processingIndex] = true;\n            palSubSeqBacktrack(s, bitmask, processingIndex + 1, palSubSeq);\n            bitmask[processingIndex] = false;\n            palSubSeqBacktrack(s, bitmask, processingIndex + 1, palSubSeq);\n            return;\n        }\n\n        // at bottom, call stage 2\n        palSubSeqRecur(s, bitmask, palSubSeq);\n    }\n\n    // stage 2, for all subsequences, do recursion call + memoization. this could be changed to iterative\n    private static int palSubSeqRecur(String s, boolean[] bitmask, int[] palSubSeq) {\n        int bitIndex = bitmaskToIndex(bitmask);\n        if (bitIndex == 0) {\n            return 0;\n        }\n        if (palSubSeq[bitIndex] != 0) {\n            return palSubSeq[bitIndex];\n        }\n\n        // all-0\'s should be handled above\n        // single characters should have been filled in as base case\n        // starting here it should have at least 2 characters (2 one\'s in the bitmask)\n        int firstOneIndex;\n        for (firstOneIndex = 0; firstOneIndex < bitmask.length; firstOneIndex++) {\n            if (bitmask[firstOneIndex]) {\n                break;\n            }\n        }\n        int lastOneIndex;\n        for (lastOneIndex = bitmask.length - 1; lastOneIndex >= 0; lastOneIndex--) {\n            if (bitmask[lastOneIndex]) {\n                break;\n            }\n        }\n\n        int max = 0;\n        // maxPalSubseq(001110011) = max{\n        //   2 + maxPalSubseq(000110010) if s[2]==s[8],\n        //   maxPalSubseq(000110011),\n        //   maxPalSubseq(001110010),\n        // }\n        if (s.charAt(firstOneIndex) == s.charAt(lastOneIndex)) {\n            bitmask[firstOneIndex] = false;\n            bitmask[lastOneIndex] = false;\n            max = 2 + palSubSeqRecur(s, bitmask, palSubSeq);\n        }\n\n        bitmask[firstOneIndex] = false;\n        bitmask[lastOneIndex] = true;\n        int altMax1 = palSubSeqRecur(s, bitmask, palSubSeq);\n\n        bitmask[firstOneIndex] = true;\n        bitmask[lastOneIndex] = false;\n        int altMax2 = palSubSeqRecur(s, bitmask, palSubSeq);\n\n        bitmask[firstOneIndex] = true;\n        bitmask[lastOneIndex] = true;\n        if (altMax1 > max) {\n            max = altMax1;\n        }\n        if (altMax2 > max) {\n            max = altMax2;\n        }\n        palSubSeq[bitIndex] = max;\n        return max;\n    }\n\n    private static int bitmaskToIndex(boolean[] bitmask) {\n        int length = bitmask.length;\n        int number = 0;\n        for (int i = 0; i < length; i++) {\n            number = bitmask[i] ? (number * 2 + 1) : (number * 2);\n        }\n        return number;\n    }\n}\n```
['Dynamic Programming', 'Backtracking', 'Java']