# 005. Longest Palindromic Substring

Difficulty: Medium

Frequency: Medium

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.

Test cases:
1. a
2. aa
3. aaa
4. aba
5. abba

Solution 1:

Data structure:
string
Method:
Two pointers
Steps:
1. For each center, expand and test whether it is a palindrome and then record its length if it is the current max.
Complexity:
Runtime: O(n^2) 168 ms
Space: O(1)
Code:
```class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n <= 1) return s;
string result;
for (int i = 0; i < 2 * n - 1; i++) {
int left = i / 2 - (i + 1) % 2, right = i / 2 + 1;
while (left >= 0 && right < n) {
if (s[left] != s[right]) break;
else {
left--;
right++;
result = result.size() < right - left - 1 ? s.substr(left + 1, right - left - 1): result;
}
}
}
return result;
}
};
```

Solution 2:
Data structure:
string
Method:
Manacher’s algorithm
steps:
see links.
Complexity:
Runtime: O(n) 16 ms
Space: O(n)
Code:
```class Solution {
public:
string longestPalindrome(string s) {
string t;
for (int i = 0; i < s.size(); i++) {
t += "#" + s.substr(i, 1);
}
t.push_back('#');

vector<int> p(t.size(), 0);
int center = 0, boundry = 0, maxLen = 0, resCenter = 0;
for (int i = 1; i < t.size() - 1; i++) {
int iMirror = 2 * center - i;
p[i] = boundry - i > 0 ? min(boundry - i, p[iMirror]) : 0;
// expand p[i]
while (i - 1 - p[i] >= 0 && i + 1 + p[i] <= t.size() - 1 && t[i - 1 - p[i]] == t[i + 1 + p[i]]) {
p[i]++;
}
// update center and boundry
if (p[i] + i > boundry) {
boundry = p[i] + i;
center = i;
}
if (p[i] > maxLen) {
maxLen = p[i];
resCenter = i;
}
}
return s.substr((resCenter - maxLen) / 2, maxLen);
}
};
```

Submission errors:
1. seg fault. Need to be careful with the range.
2. TLE. Solution is not good enough.

Things to learn:

1. When need to handle even and odd in string or array, examples will help.
2. Manacher’s algorithm is quite interesting, but don’t know whether it is useful for other problems.
Advertisements

## 2 thoughts on “005. Longest Palindromic Substring”

1. […]  Longest Palindromic Substring […]

Like