int longestPalindromeSubseq(const string& s) {
    string t(s);
    reverse(t.begin(), t.end());
    const int kN = s.size();
    vector<vector<int>> longest_palindr_dp(kN + 1, vector<int>(kN + 1));

    for (int i = 1; i <= kN; ++i) {
      for (int j = 1; j <= kN; ++j) {
        int max_sofar = 0;
        if (s[i - 1] == t[j - 1])
          max_sofar = max(max_sofar, longest_palindr_dp[i-1][j-1] + 1);
        else
          max_sofar = max({max_sofar, longest_palindr_dp[i][j-1], longest_palindr_dp[i-1][j]});

        longest_palindr_dp[i][j] = max_sofar;
      }
    }

    return longest_palindr_dp.back().back();
  }