2016-09-25 @sunderls

following solutions are all created by myself, if I didn't tackle it and got solution from editorial solution, it will be made clear at the heading.

https://leetcode.com/problems/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.

For input such as `"abcbd"`

, we should return "bcb". Of course we can just scan every sub string(at account of A(n,2)), so complexity is O(n^{3}).

- We we are judging whether a string is palindromic, we compare the characters from head & tail, one by one. What if we start if from the middle? worst case is the same ==> for all same characters like
`"aaaaaa"`

- Can we cut off the head & tail?
`"abcbd"`

, since head & tail is not the same, so longest must be in`"abcb"`

or`"bcbd"`

. Respectively for`"abcb"`

, we check`"abc"`

,`"bcb"`

....===> seems not helping - If we focus on the center line of palindromic, we can get O(n) * 2n = O(n
^{2}), this seems also not ideal. - Since palindromic strings are the same event reversed, for
`"abcbde"`

, and its reversed version`"ebbcba"`

, if we place them together, the longest same substring i the palindromic string, is this helping?No this assumption is wrong =>`"abcedcba"`

& its reversed version will not satisfy. - continue with 3, if all the characters are not same, each comparison will finish in after one time, so complexity is really just O(1) * 2n = O(n), which seems promising, what about when we found some ? like
`"abcbd"`

, we we got to`"bcb"`

, now since first "bc" is already checked, we can just jump to "b", eh? seems promising, we can avoid rechecking characters within a palindromic substring by remembering how much we can jump ahead? Possible? for example:`"abcbcbcbcd"`

, the length is 0(0)0(0)1(0)2(0)1(0)0(0)0(1)1(1)0., for`"aaaaaaa"`

, the index is : 0(1)1(2)2(3)3(3)2(2)1(1)0. so every time of comparing, a new character is taken in consideration, so complexity is O(n), right?

to simplify it , we consider above string as `"a-b-c-b-c-b-c-b-c-d"`

, and collect the right string at the end

```
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
// we suppose there is a hyphen between the characters to simply our thinking
// character at even index is original character
// character at odd index is original no existing
var total = s.length * 2 - 1;
// we use an array to store the max range at specific index
var steps = [];
// maxLength of polindromic sub string
var maxLength = 1;
// start index (real);
var resultStartIndex = 0;
// tempary substring length & start
var length = 0;
var start = 0;
for (var i = 0; i <= total - 1; i++){
var lastStep = steps.length > 0 ? steps[steps.length - 1] : 0;
// [ATTETION]
// the step should be either lastStep - 1 or mirror element's step
step = lastStep > 1 ? Math.min(steps[steps.length - 2], lastStep - 1) : 0;
while(i - step - 1 > -1 && i + step + 1 < total && ((i - step - 1) % 2 === 1 || s[(i - step - 1) / 2] === s[(i + step + 1) / 2])){
step += 1;
}
steps.push(step);
if (i % 2 === 1){
if (step % 2 === 1){
start = i - step;
length = step + 1;
} else {
start = i - step + 1;
length = step;
}
} else {
if (step % 2 === 1){
start = i - step + 1;
length = step;
} else {
start = i - step;
length = step + 1;
}
}
// update max
if (length > maxLength){
resultStartIndex = start / 2;
maxLength = length;
}
}
return s.slice(resultStartIndex, resultStartIndex + maxLength);
};
```

Made some mistakes at possibility that inferring current step by mirror element is error because of out of range from previous element. While other things went well at 96ms

The Editorial Solution gives us many considerable solutions

- Common SubString by reversing it, well I actually considered it and find it not very easy. The flaw which I said above can be rectified by simple checking, and according to editorial solution, this is another problem in O(n
^{2}) - Brute Force, same as my analysis.
- Dynamic Programming at time: O(n
^{2}) & space: O(n^{2}) - Expand Around Center which is the solution pointed above as analysis 3
- Manacher's Algorithm: Wow in fact this is the same as above solution. detail is here : http://articles.leetcode.com/longest-palindromic-substring-part-ii/.

And actually, I think many problems can be solved with better solutions by thinking about reducing calculations based results already got when traversing. Give me a high-five.