Palindrome Game Hard

Alice and Bob play a game with string s. Players alternate picking either the leftmost or rightmost character of the remaining string and adding it to the end of their own string. After all characters are taken, each player scores the length of the longest palindromic subsequence (LPS) in their own string. Alice wins if her score is strictly greater than Bob's. Both play optimally — determine if Alice has a winning strategy.

Examples
Input: "abca"
Output: false
Hints

Palindrome Game Hard

Alice and Bob play a game with string s. Players alternate picking either the leftmost or rightmost character of the remaining string and adding it to the end of their own string. After all characters are taken, each player scores the length of the longest palindromic subsequence (LPS) in their own string. Alice wins if her score is strictly greater than Bob's. Both play optimally — determine if Alice has a winning strategy.