LPS

    string longestPalindrome(string s) {
        int dp[1005][1005] = {0};
        int len = 1, n = s.size(), start = 0;
        for (int i = 0; i < n; i++){
            dp[i][i] = 1;
            for (int j = 0; j < i; j++){
                dp[j][i] = (s[i] == s[j] && (i-j < 2 || dp[j+1][i-1]));
                if (dp[j][i] && len < i-j+1){
                    len = i - j + 1, start = j;
                }
            }
        }
        //cout << len << " " << start;
        return s.substr(start, len);
    }