Create an adjacency matrix adj[i][j] denoting if the character i can be followed by the character j.
Say you fix the first character, and denote it as a (but the character itself doesn’t have to be a). Then the last character has to be equal to that. Now the second character has to be equal to the second-last character as well. What are possible candidates for the second character (denoted as b in the same fashion)? Only characters where adj[b][a] and adj[a][b], because it has to be both after a and before a.
So from that you can compute the answer from outside in (or inside out) in a DP-like manner. Be careful when placing the center characters for an even-length string, because you have the additional constraint that adj[b][b] must be true. Total complexity is O(n \cdot \alpha^2) where \alpha = 26.
Dunno why I answered this, it’s such a low-effort question, but whatever
Thanks , I got it .