Problem statement:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"Output: "bab"Note: "aba" is also a valid answer.

Example:

Input: "cbbd"Output: "bb"

Solution:

Compare with 516. Longest Palindromic Subsequence, the difference is the subsequence and substring, subsequence does not require all the palindrome is in a row, however, substring must be a consective string. The dynamic programming formula is a little bit different.

dp[i][j] meas s(i, j) is a palindrome or not, if it is the length is j - i + 1;

dp[i][j] is true only s[i] == s[j] and dp[i + 1][j - 1] also is true ( or i and j is consective or there is only one element between i and j).

Each time find a palindrome,  we should compare with previous one and update.

class Solution {public:    string longestPalindrome(string s) {        int size = s.size();        int dp[size][size] = {};        string ans("");        for(int i = size - 1; i >= 0; i--){            for(int j = i; j < size; j++){                if(s[i] == s[j] && (j - i < 3 || dp[i + 1][j - 1])){                    dp[i][j] = 1;                    if(ans.empty() || j - i + 1 > ans.size()){                        ans = s.substr(i, j - i + 1);                    }                }            }        }        return ans;    }};

5. Longest Palindromic Substring