JavaScript accepted solution worst O(n^2) with optimization [116ms beats 96.23%]


  • 3
    R

    The idea is: there are 2 kinds of palindrome string, 'abcba' with no repeated characters; 'bccccb' or 'cccc' with repeated characters, and it doesn't matter the number of repeated chars is odd or even;

    So we try to find any repeated sub-strings, and for each such string, we check the chars around it and count the length, record the head/tail index if it's the largest so far.

    Example, 'zabccccccbxt', first we try to find any repeated chars, like 'cccccc', note that any number of 'c' is palindrome, so we can skip them, jump to the last 'c', then we check chars around 'cc', we get 'bccccccb', length 8;
    Any non-repeated char is just a special case, like 'z', its length is 1, 'a' is the same, length is 1; Then we can check chars around it just like repeated chars;

    I think the worst case could be something like 'aabbccddeeffgg........................', in which case O(n^2);
    Other cases are pretty fast;
    I could be wrong, comments are welcome.

    /**
     * @param {string} s
     * @return {string}
     */
    var longestPalindrome = function(s) {
      var head,
      	tail,
        i,
        len = s.length,
        count,
        maxCount = 0,
        offset,
        result = [-1, -1];
      
      for (i = 0; i < len; i++) {
        head = i;
        while (i < len - 1 && s.charAt(i) === s.charAt(i+1)) {
          i++;
        }
        tail = i;
        count = tail - head + 1;
        
        for (offset = 1; offset <= Math.min(head, len - tail - 1); offset++) {
          if (s.charAt(head - offset) === s.charAt(tail + offset)) {
            count += 2;
          } else {
            break;
          }
        } 
        if (count > maxCount) {
          result[0] = head - offset + 1;
          result[1] = tail + offset - 1;
          maxCount = count;
          //$('#log').append('<p>' + result + '</p>');
          //$('#log').append('<p>' + maxCount + '</p>');
        }
      }
      
      return s.substring(result[0], result[1] + 1);
    };

  • 1

    You can add if(len-i>manCount/2) break; in the end of the loop.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.