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:
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.