``````class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if(n < 2) return s;
int maxlen = 1,begin = 0;
for(int i = 0;i < n - 1;i++)
{
for(int j = i + 1;j < n;j++)
{
if(j - i + 1 > maxlen && isvalidPalindome(s,i,j))
{
begin = i;
maxlen = j -i + 1;
}
}
}

return s.substr(begin,maxlen);
}
private:
bool isvalidPalindome(string s,int i,int j){
while(i < j)
{
if(s[i++] != s[j--]) return false;
}

return true;
}
};``````

``````47 / 176 test cases passed.
Status: Time Limit Exceeded
Submitted: 0 minutes ago
Last executed input:
"ibvjkmpyzsifuxcabqqpahjdeuzaybqsrsmbfplxycsafogotliyvhxjtkrbzqxlyfwujzhkdafhebvsdhkkdbhlhmaoxmbkqiwius……"``````

#### 动态规划

dp[i][j]=dp[i+1][j-1] ^(s[i] == s[j])

dp[i][i] = 1
dp[i][j] = 1 (if(s[i] == s[j])

``````class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
vector<vector<int>> dp(n,vector<int>(n,0));
string ans;
for(int step = 0; step < n;step++)
{
for(int i = 0;i + step < n;i++)
{
int j = i + step;
if(step == 0)
dp[i][j] = 1;
else if(step == 1)
dp[i][j] = (s[i] == s[j]);
else
{
dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1];
}

if(dp[i][j] && (j - i + 1 > ans.size()))
ans = s.substr(i,j-i+1);
}
}

return ans;
}
};``````

#### 2021.05.03更新

``````class Solution {
public:
string longestPalindrome(string s) {
if(s.size() == 1 || s.empty() )
{
return s;
}
int maxLen= 1;
int minbegin = 0;
for(int i=0; i<s.size();)
{
int l = i;
int r = i;
if(s.size()-i <=maxLen/2)
break;
while(r<s.size()&&s[r]==s[r+1])
r++;
i = r +1;
while(l>=0&&r<s.size()&&s[l]==s[r])
{
l--;
r++;
}
if(r-l-1 > maxLen)
{
maxLen = r-l-1;
minbegin =l+1;
}
}
return s.substr(minbegin, maxLen);
}
};``````

``````Runtime: 4 ms, faster than 99.71% of C++ online submissions for Longest Palindromic Substring.
Memory Usage: 6.9 MB, less than 99.03% of C++ online submissions for Longest Palindromic Substring``````

````
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if(n <= 1)
{
return s;
}
int maxLen= 1;
int minbegin = 0;
for(int i = 0; i < n;)
{
int l = i,r = i;
if(n - i <= maxLen/2)
break;
while(r r++;
i = r +1;
while(l>=0&&r {
l--;
r++;
}
if(r-l-1 > maxLen)
{
maxLen = r-l-1;
minbegin =l+1;
}
}
return s.substr(minbegin, maxLen);
}
};

``程序运行效率：``

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Longest Palindromic Substring.
Memory Usage: 7 MB, less than 94.35% of C++ online submissions for Longest Palindromic Substring.
```