javascriptalgorithmpalindrome

Longest palindrome in a string


I wrote the following function to find the longest palindrome in a string. It works fine but it won't work for words like "noon" or "redder". I fiddled around and changed the first line in the for loop from:

var oddPal = centeredPalindrome(i, i);

to

var oddPal = centeredPalindrome(i-1, i);

and now it works, but I'm not clear on why. My intuition is that if you are checking an odd-length palindrome it will have one extra character in the beginning (I whiteboarded it out and that's the conclusion I came to). Am I on the right track with my reasoning?

var longestPalindrome = function(string) {

  var length = string.length;
  var result = "";

  var centeredPalindrome = function(left, right) {
    while (left >= 0 && right < length && string[left] === string[right]) {
      //expand in each direction.
      left--;
      right++;
    }

    return string.slice(left + 1, right);
  }; 

  for (var i = 0; i < length - 1; i++) {
    var oddPal = centeredPalindrome(i, i); 
    var evenPal = centeredPalindrome(i, i);

    if (oddPal.length > result.length)
      result = oddPal;
    if (evenPal.length > result.length)
      result = evenPal;
  }

  return "the palindrome is: " + result + " and its length is: " + result.length;
};

UPDATE: After Paul's awesome answer, I think it makes sense to change both variables for clarity:

var oddPal  = centeredPalindrome(i-1, i + 1);
var evenPal = centeredPalindrome(i, i+1);

Solution

  • You have it backwards - if you output the "odd" palindromes (with your fix) you'll find they're actually even-length.

    Imagine "noon", starting at the first "o" (left and right). That matches, then you move them both - now you're comparing the first "n" to the second "o". No good. But with the fix, you start out comparing both "o"s, and then move to both "n"s.

    Example (with the var oddPal = centeredPalindrome(i-1, i); fix):

    var longestPalindrome = function(string) {
    
      var length = string.length;
      var result = "";
    
      var centeredPalindrome = function(left, right) {
        while (left >= 0 && right < length && string[left] === string[right]) {
          //expand in each direction.
          left--;
          right++;
        }
    
        return string.slice(left + 1, right);
      };
    
      for (var i = 0; i < length - 1; i++) {
        var oddPal = centeredPalindrome(i, i + 1);
    
        var evenPal = centeredPalindrome(i, i);
    
        if (oddPal.length > 1)
          console.log("oddPal: " + oddPal);
        if (evenPal.length > 1)
          console.log("evenPal: " + evenPal);
    
        if (oddPal.length > result.length)
          result = oddPal;
        if (evenPal.length > result.length)
          result = evenPal;
      }
      return "the palindrome is: " + result + " and its length is: " + result.length;
    };
    
    console.log(
      longestPalindrome("nan noon is redder")
    );