CODEWITHSUNDEEP
javascriptstringtime-complexity
myTest532 myTest532
myTest532 myTest532

Reputation: 2381

Longest Palindromic Substring in Javascript

I'm trying to solve the Longest Palindromic Substring problem in O(N^2) time complexity.

Problem: 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"

My solution:

var longestPalindrome = function(s) {
    if(!s || s.length === 0)    return "";
    
    let start = 0;
    let end = 0;
    
    for(let i=0; i<s.length; i++) {
        let len1 = expand(s, i, i);
        let len2 = expand(s, i, i+1);
        let size = Math.max(len1, len2);
        if(size > end-start) {
            start = Math.floor(i - ((size-1) / 2));
            end = Math.floor(i + (size/2));
        }
    }
    
    return s.substring(start, end+1);
};

const expand = (str, left, right) => {
    let l = left;
    let r = right;
    while(l >= 0 && r < str.length && str[l] === str[r]) {
        l--;
        r++;
    }
    
    return r-l-1;
}

My solution works for the example 1, but it fails for the example 2. It returns "cbb" instead of "bb". Does anyone know what I'm doing wrong?

Thanks

Upvotes: 0

Views: 2381

Answers (2)

Carsten Massmann
Carsten Massmann

Reputation: 28206

For illustration only:
the following will work but, obviously, it is not O(n^2)!

["babad","dessert","the fastest racecar was his","A reviver.","boring"].forEach(s=>
  console.log(s+': '+longpal(s)));
  
function longpal(s){
  let r=s.split('').reverse().join(''); // reverse string
  let p,l,m=[0,0]; // [pos,len] of best match
  for(p=0;p<s.length;p++){   
   for(l=s.length-p; l>m[1];l--)
    // remember p and l only if it is a longer match 
    if (r.indexOf(s.substr(p,l))>-1) m=[p,l];
  } 
  return s.substr(...m)
}

Upvotes: -1

Jacob Steinebronn
Jacob Steinebronn

Reputation: 863

Simple enough, replace

start = Math.floor(i - ((size-1) / 2));

with

start = i - Math.floor((size-1) / 2);

Your complexity will be, as you outlined earlier, O(n^2). If you care, it's possible to get O(n log(n)), but this technique is considerably more difficult. It involves hashing the corpus(input string) in such a way that you can get substring hashes in O(1) with O(n) precomp, then for each start character (or pair of adjacent similar characters) binary search your way to the LPS at that index (so you'll need reverse hashes as well). I'm sure you can find a better explanation somewhere out there on the internet. GL!

Upvotes: 2

Related Questions