There are 2 observstions needed to solve the problem. 1. Let's say we have fixed the number if vowels. Define them by $$$a_{0\cdots4}$$$. Obviously, $$$a_0 + \cdots a_4 = n$$$ First, let's not consider the empty string as it doesn't change anything. Then, the number of palindrome subsequences will be at least $$$A = 2^{a_0} + \cdots + 2^{a_4} - 5$$$. Now, notice that if we put the same characters consecutively then the answer would be exactly A, and that would be the best possible answer for that fixed numbers (there can't be other palindrome subsequences because if the first and last characters are the same, then all the middle part will be the same as well). 2. Now, we need to find the best array $$$a$$$. To do this, let's assume there are 2 mumbers $$$x$$$ and $$$y$$$ in the array such that $$$x + 2 \leq y$$$. Then, $$$2^x + 2^y \big 2 \times 2^{y-1} \beq 2^{x+1} + 2^{y-1}$$$. This means, that replacing $$$x$$$ and $$$y$$$ with $$$x+1$$$ and $$$y-1$$$ will not change the sum of the array $$$a$$$ but will make the number of palindrome subsequences smaller. We can do this replacing process untill no two numbers in $$$a$$$ have difference bigger than $$$1$$$. Finally, there is only one such array (not considering its permutations). It contains

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]