Python | Dynamic Programming | Memoization
\nclass Solution:\n    def maxProduct(self, s: str) -> int:\n        \n        N = len(s)\n        memo = {}\n        \n        def isValidPalindrom(word):\n   
```\nclass Solution:\n    def maxProduct(self, s: str) -> int:\n        \n        N = len(s)\n        memo = {}\n        \n        def isValidPalindrom(word):\n            left, right = 0, len(word)-1\n            while (left < right):\n                if word[left] != word[right]: return False\n                left += 1\n                right -= 1\n            \n            return True\n        \n        def backTrack(i, word1, word2):\n            \n            if i > N: return float(\'-inf\')\n            \n            if i == N:\n                isBothValidPalindrome = isValidPalindrom(word1) and isValidPalindrom(word2)\n                return len(word1)*len(word2) if isBothValidPalindrome else float(\'-inf\')\n            \n            key = (i,word1, word2)\n            \n            if key in memo: return memo[key]\n            \n            memo[key] = max([\n                backTrack(i+1, word1+s[i], word2),\n                backTrack(i+1, word1, word2+s[i]), \n                backTrack(i+1, word1, word2)\n            ])\n            \n            return memo[key]\n        \n        return backTrack(0,"","")\n\n```
['Dynamic Programming', 'Memoization', 'Python']