Brute force: Bitmask + Longest Palindromic Subsequence
Generate all possible splits of s into two sequences of minimum 1 character (using bitmask).\nRun the longest palindromic subsequence algorithm on both parts an
Generate all possible splits of s into two sequences of minimum 1 character (using bitmask).\nRun the[ longest palindromic subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/) algorithm on both parts and return the max encountered product.\n\n```\nclass Solution {\n    public int maxProduct(String s) {\n        char[] ca= s.toCharArray();\n        int n= ca.length, k= 1 << n, max= 1;\n        char[] seq1= new char[12], seq2= new char[12];\n        for(int i=1; i<k-1; i++){\n            int n1= 0, n2= 0;\n            for(int j= 0; j<n; ++j){\n                if((i & (1<<j)) != 0) seq1[n1++]= ca[j];\n                else seq2[n2++]= ca[j];\n            }\n            int lps1= lps(seq1, 0, n1-1), lps2= lps(seq2, 0, n2-1);\n            max= Math.max(max, lps1*lps2);\n        }\n        return max;\n    }\n\n    int lps(char[] seq, int i, int j) {\n        if(i==j) return 1;\n        if(seq[i]==seq[j] && i+1 == j) return 2;\n        if(seq[i]==seq[j]) return lps(seq, i+1, j-1) + 2;\n        return Math.max(lps(seq, i, j-1), lps(seq, i+1, j));\n    }\n}
['Bitmask']