void palindrome(const string& s, vector<vector<int>>& cache) {
    vector<vector<int>> leftMost(s.size());
    vector<int> D(26, -1);
    for (int i=s.size()-1; i >= 0; i--) {
        D[s[i]-'a'] = i;
        leftMost[i] = D;
    }
    for (int i=0; i < s.size(); i++) cache[i][i] = 1;
    for (int L=2; L <= s.size(); L++) {
        for (int j=L-1; j < s.size(); j++) {
            int i = j-L+1;
            if (leftMost[i][s[j]-'a'] == j) cache[i][j] = cache[i][j-1];
            else if (leftMost[i][s[j]-'a'] == j-1) cache[i][j] = max(cache[i][j-1], 2);
            else cache[i][j] = max(cache[i][j-1], cache[leftMost[i][s[j]-'a']+1][j-1]+2);
        }
    }
}

int playWithWords(const string& s) {
    vector<vector<int>> cache(s.size(), vector<int>(s.size()));
    palindrome(s, cache);
    int result = 0;
    for (int i=0; i < s.size()-1; i++) result = max(result, cache[0][i] * cache[i+1][s.size()-1]);
    return result;
}