Description
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd" Output: "bb"
Submission
The following solution should be the most straight forward one. The main idea is to focus on the central point of the palindrome. And for each central point, find the possible symmetry around it. It can be generalized into 2 stages. The first stage is to find the same characters around the central character. And the second stage is to find out the ones different but match on both sides. The whole process can be finished with only 3 for loops.
class Solution {
public String longestPalindrome(String s) {
int curr_len = 0;
int res_len = 0;
int res_start = 0;
int left, right;
if(s.length() == 0 || s.length() == 1) return s;
for(int i = 0; i < s.length(); i++) {
curr_len = 1;
left = i - 1;
right = i + 1;
// "bbaaaaaaaaaabc"
for(; left >= 0 && s.charAt(left) == s.charAt(i); left--, curr_len++);
for(; right < s.length() && s.charAt(right) == s.charAt(i); right++, curr_len++);
for(;left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right);
left--, right++, curr_len += 2);
if(curr_len > res_len) {
res_len = curr_len;
res_start = left + 1;
}
}
return s.substring(res_start, res_start + res_len);
}
}
Failed Attempt
Before my first successful submission, I tried to use a stack to find that, but it turned out to be a naive first thought. When it comes to cases like “bananas” where you cannot decide where the center of the palindrome substring is, you can hardly solve the problem. So I referred to the solution and changed my mindset.
class Solution {
public String longestPalindrome(String s) {
char [] stack = new char[1000];
int i, p = 0;
int res_end = 0;
int res_len = 0;
int curr_len = 0;
int prev_state = 2;
if(s.length() == 0 || s.length() == 1) return s; // "a" or ""
char c = s.charAt(0);
char prev_c = c;
int prev_i = 0;
for(i = -1; i < s.length() - 1;) {
i++;
prev_c = c;
c = s.charAt(i);
if(prev_state == 0 && prev_c == c) { // "ccc"
curr_len++;
} else if(p - 1 >= 0 && stack[p - 1] == c) {
p--; // "aa"
curr_len += 2;
prev_state = 0;
} else if (p - 2 >= 0 && stack[p - 2] == c && curr_len == 0 &&
s.charAt(i + 1) != s.charAt(i - 1)) {
p -= 2; // "aba"
curr_len += 3;
prev_state = 1;
} else {
if(res_len < curr_len) {
res_end = i;
res_len = curr_len;
}
if(prev_state < 2) {
i -= curr_len;
curr_len = 0;
prev_state = 2;
continue;
}
stack[p++] = c;
if(res_len == 0) { // "ac"
res_len = 1;
res_end = p;
}
prev_state = 2;
}
}
if(res_len < curr_len) {
res_end = i + 1;
res_len = curr_len;
}
return s.substring(res_end - res_len,res_end);
}
}
Solutions
The best way to solve the problem in O(N) is to use the Manacher’s Algorithm. The crux is to use the scope of the so-far furthest expansion Palindrome substring. In a so-far furthest expansion Palindrome substring, one major property is the symmetry. On the right half of the palindrome, each substring should have a mirror on the other side. If the left one is totally inside the scope, the right mirror of it should be the same, otherwise, the right one should expand itself with the basis of the part of it inside the scope. Since we scan the string from left to right one by one, the left one is calculated before the right one, so the result of the left one can always be used by the right one.
Another technique to apply is to insert a special character, for example, “#”(Hashtag), between every 2 characters and on both sides so that an even length palindrome case can be transformed to an odd one. The only thing to do in the end is to solve the equation 2 * res + 1 = curr_res, where res is the real palindrome length, and curr_res is the length of the palindrome after the transformation.
To see how it works, you can refer to:
To note that the final result should be (maxLen – 1) / 2 instead of maxLen.