Bitmask approach in TypeScript
Approach\n1. Use bit mask to get all possible subsequences.\n2. If subsequence is palindrome, add [bitmask, length] pair to array.\n3. Iterate through all pairs
# Approach\n1. Use bit mask to get all possible subsequences.\n2. If subsequence is palindrome, add `[bitmask, length]` pair to array.\n3. Iterate through all pairs in array. If two bitmasks are disjoint, `(bitmask1 & bitmask2) === 0`.\n4. Return max length product.\n\n# Complexity\nIn worst case, we have 2^n `[subseq, length]` pairs in `subseqLengthPairs`\n- Time complexity\n`O((2^n)^2) = O(4^n)`\n\n- Space complexity:\n`O(2^n)`\n\n# Code\n```TypeScript\nconst palindromeMemo = {};\nfunction maxProduct(s: string): number {\n    // all [ palindromic subseq, length ] pairs\n    const subseqLengthPairs: Array<Array<number>> = []\n    for (let i = 0; i < 1 << s.length; i++) {\n        const subseq = bitmaskToSubseq(s, i);\n        if (isPalindrome(subseq)) {\n            subseqLengthPairs.push([i, subseq.length]);\n        }\n    }\n\n    let res = 0\n    for (const [bitmask1, length1] of subseqLengthPairs) {\n        for (const [bitmask2, length2] of subseqLengthPairs) {\n            if ((bitmask1 & bitmask2) === 0) {\n                // two subeq are disjoint\n                res = Math.max(res, length1 * length2);\n            }\n        }\n    }\n    return res;\n};\n\nconst bitmaskToSubseq = (s: string, bitmask: number): string => {\n    let subseq = "";\n    for (let i = 0; i < s.length; i++) {\n        if (((1 << i) & bitmask) !== 0) {\n            subseq += s.charAt(i);\n        }\n    }\n    return subseq;\n}\n\nconst isPalindrome = (s: string): boolean => {\n    if (palindromeMemo?.[s] !== undefined) {\n        return palindromeMemo[s];\n    }\n    let l = 0;\n    let r = s.length - 1;\n    while (l < r) {\n        if (s.charAt(l) !== s.charAt(r)) {\n            palindromeMemo[s] = false;\n            return false;\n        }\n        l++; r--;\n    }\n    palindromeMemo[s] = true;\n    return true\n}\n```
['Bit Manipulation', 'Bitmask', 'TypeScript']