all articles

leetcode war 5 - Longest Palindromic Substring

2016-09-25 @sunderls

leetCode

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.

leetcode war :Longest Palindromic Substring

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.

Analysis - Brute Force.

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(n3).

  1. 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"
  2. 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
  3. If we focus on the center line of palindromic, we can get O(n) * 2n = O(n2), this seems also not ideal.
  4. 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.
  5. 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

code

/**
 * @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

Editorial Solution

The Editorial Solution gives us many considerable solutions

  1. 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(n2)
  2. Brute Force, same as my analysis.
  3. Dynamic Programming at time: O(n2) & space: O(n2)
  4. Expand Around Center which is the solution pointed above as analysis 3
  5. 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.