# [leetcode] Longest Palindromic Substring

### Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

tag: string

9/23/2015 update

Same algorithm as described as follows, but neater I think.

```class Solution {
public:
string longestPalindrome(string s) {
int len = s.size();
string ans;
for(int i = 0; i < len; i++){
//i is the center of the possible palindromic substring
int j = 0; //half length of the substring
//odd palindrome
while(i - j >= 0 && i + j < len && s[i - j] == s[i + j]){
j++;
}
int substrlen = 2 * j - 1;
ans = substrlen > ans.size()? s.substr(i - j + 1, substrlen): ans;

//even palindrome
j = 0;
while(i - j >= 0 && i + j + 1 < len && s[i - j] == s[i + j + 1]){
j++;
}
substrlen = 2 * j;
ans = substrlen > ans.size()? s.substr(i - j + 1, substrlen): ans;
}
return ans;
}
};```

```class Solution {
public:
string longestPalindrome(string s) {
string re;
if (s.empty()){
return re;
}
for(int mid = 0; mid < s.size(); mid++){//odd string
int halfLength;
for(halfLength = 0; mid - halfLength >= 0 && mid + halfLength < s.size(); halfLength++){
if(s[mid - halfLength] == s[mid + halfLength]){
continue;
}
else{
break;
}
}
halfLength--;//don't forget this line. halfLength means first not acceptable substring before this line is executed
if (halfLength * 2 + 1 > re.size()){
re = s.substr(mid - halfLength, halfLength * 2 + 1);
}
}
for (int leftMid = 0; leftMid + 1 < s.size(); leftMid++){//even string
int halfLength;
for(halfLength = 0; leftMid - halfLength >= 0 && leftMid + 1 + halfLength < s.size(); halfLength++){
if(s[leftMid - halfLength] == s[leftMid + 1 + halfLength]){
continue;
}
else{
break;
}
}
halfLength--;
if (halfLength * 2 + 2 > re.size()){
re = s.substr(leftMid - halfLength, halfLength * 2 + 2);
}
}
return re;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.