Longest palindrome in a string

Question

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);

Heptad

YES - that finally makes sense. of course you would do i+1 for EVEN palindromes because their "center" would be 2 instead of 1 for odds. Thanks! – Heptad

I think this might be more intuitive, editing above also: var oddPal = centeredPalindrome(i-1, i + 1); var evenPal = centeredPalindrome(i, i+1); – Heptad

I just wanted to point out there is a fast linear time algorithm for this problem know as Manacher's algorithm. – Overanxious

Answer 1

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")
);

Softhearted

I don't think this code checks for spaces. So if for example you ran longestPalindrome("a level b"); you would get the longest palindrome as " level " with a length of 7. – Kierkegaard

True, though out of scope of (my reading of) the question. Definitely consider adding your own answer that solves that part of the problem. – Softhearted

Running this code gave me: the palindrome is: noon and its length is: 6 - should that be redder instead? – Kraemer

As mentioned in an above comment, it doesn't treat spaces any differently than non-spaces. It's finding " noon " (leading and trailing space), which is 6 chars long just like redder. That's a thing that should be fixed, but a separate problem from this particular question. – Softhearted

Here loop must be run to less the length for (var i = 0; i < length - 1; i++) ==> for (var i = 0; i < length; i++) – Breastfeed

@Breastfeed If we made that change, what would happen when we reference the i + 1 element? – Softhearted

Answer 2

Here is another take on the subject.

• Checks to make sure the string provided is not a palindrome. If it is then we are done. ( Best Case )
• Worst case 0(n^2)

link to gist

Use of dynamic programming. Break each problem out into its own method, then take the solutions of each problem and add them together to get the answer.

class Palindrome {
   constructor(chars){
     this.palindrome = chars;
     this.table = new Object();
     this.longestPalindrome = null;
     this.longestPalindromeLength = 0;

     if(!this.isTheStringAPalindrome()){
      this.initialSetupOfTableStructure();
     }
   }

   isTheStringAPalindrome(){
     const reverse = [...this.palindrome].reverse().join('');
     if(this.palindrome === reverse){
       this.longestPalindrome = this.palindrome;
       this.longestPalindromeLength = this.palindrome.length;
       console.log('pal is longest', );
       return true;
     }
   }

   initialSetupOfTableStructure(){
     for(let i = 0; i < this.palindrome.length; i++){
       for(let k = 0; k < this.palindrome.length; k++){
        this.table[`${i},${k}`] = false;
       }
     }
     this.setIndividualsAsPalindromes();
   }

   setIndividualsAsPalindromes(){
    for(let i = 0; i < this.palindrome.length; i++){
      this.table[`${i},${i}`] = true;
    }
    this.setDoubleLettersPlaindrome();
   }

   setDoubleLettersPlaindrome(){
     for(let i = 0; i < this.palindrome.length; i++){
       const firstSubstring = this.palindrome.substring(i, i + 1);
       const secondSubstring = this.palindrome.substring(i+1, i + 2);
      if(firstSubstring === secondSubstring){
       this.table[`${i},${i + 1}`] = true;

       if(this.longestPalindromeLength < 2){
         this.longestPalindrome = firstSubstring + secondSubstring;
         this.longestPalindromeLength = 2;
       }
      }
     }
     this.setAnyPalindromLengthGreaterThan2();
   }

   setAnyPalindromLengthGreaterThan2(){
     for(let k = 3; k <= this.palindrome.length; k++){
      for(let i = 0; i <= this.palindrome.length - k; i++){
        const j = i + k - 1;
        const tableAtIJ = this.table[`${i+1},${j-1}`];
        const stringToCompare = this.palindrome.substring(i, j +1);
        const firstLetterInstringToCompare = stringToCompare[0];
        const lastLetterInstringToCompare = [...stringToCompare].reverse()[0];
        if(tableAtIJ && firstLetterInstringToCompare === lastLetterInstringToCompare){

          this.table[`${i},${j}`] = true;

          if(this.longestPalindromeLength < stringToCompare.length){
            this.longestPalindrome = stringToCompare;
            this.longestPalindromeLength = stringToCompare.length;
          }
        }
      }
     }
   }

   printLongestPalindrome(){
     console.log('Logest Palindrome', this.longestPalindrome);
     console.log('from /n', this.palindrome );
   }

   toString(){
     console.log('palindrome', this.palindrome);
     console.log(this.table)
   }
 }

 // const palindrome = new Palindrome('lollolkidding');
 // const palindrome = new Palindrome('acbaabca');
 const palindrome = new Palindrome('acbaabad');
 palindrome.printLongestPalindrome();
 //palindrome.toString();

Foulness

Answer 3

This will be optimal if the largest palindrome is found earlier. Once its found it will exit both loops.

function isPalindrome(s) {
      //var rev = s.replace(/\s/g,"").split('').reverse().join('');  //to remove space
      var rev = s.split('').reverse().join('');
      return s == rev;
    }

    function longestPalind(s) {
      var maxp_length = 0,
        maxp = '';
      for (var i = 0; i < s.length; i++) {
        var subs = s.substr(i, s.length);
        if (subs.length <= maxp_length) break; //Stop Loop for smaller strings
        for (var j = subs.length; j >= 0; j--) {
          var sub_subs = subs.substr(0, j);
          if (sub_subs.length <= maxp_length) break; // Stop loop for smaller strings
          if (isPalindrome(sub_subs)) {

              maxp_length = sub_subs.length;
              maxp = sub_subs;

          }
        }
      }
      return maxp;
    }

Suffering

Answer 4

function longestPalindrome(str){
   var arr = str.split("");
   var endArr = [];

   for(var i = 0; i < arr.length; i++){
       var temp = "";
       temp = arr[i];
       for(var j = i + 1; j < arr.length; j++){
          temp += arr[j];
          if(temp.length > 2 && temp === temp.split("").reverse().join("")){
             endArr.push(temp);
          }
   }
}

var count = 0;
var longestPalindrome = "";
for(var i = 0; i < endArr.length; i++){
   if(count >= endArr[i].length){
     longestPalindrome = endArr[i-1]; 
   }
   else{
      count = endArr[i].length;
   }
 }
 console.log(endArr);
 console.log(longestPalindrome);
 return longestPalindrome;
}

longestPalindrome("abracadabra"));

Butterwort

Answer 5

function longest_palindrome(s) {
  if (s === "") {
    return "";
  }
  let arr = [];
  let _s = s.split("");
  for (let i = 0; i < _s.length; i++) {
    for (let j = 0; j < _s.length; j++) {
      let word = _s.slice(0, j + 1).join("");
      let rev_word = _s
        .slice(0, j + 1)
        .reverse()
        .join("");
      if (word === rev_word) {
        arr.push(word);
      }
    }
    _s.splice(0, 1);
  }
  let _arr = arr.sort((a, b) => a.length - b.length);
  for (let i = 0; i < _arr.length; i++) {
    if (_arr[arr.length - 1].length === _arr[i].length) {
      return _arr[i];
    }
  }
}

longest_palindrome('bbaaacc')
//This code will give you the first longest palindrome substring into the string

Protagonist

Answer 6

    let str = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
    let rev = str.split("").reverse().join("").trim();
    let len = str.length;
    let a="";
    let result = [];
    for(let i = 0 ; i < len ; i++){
        for(let j = len ; j > i ; j--){
            a = rev.slice(i,j);
            if(str.includes(a)){
                result.push(a);
                break;
            }
        }
    }
    result.sort((a,b) => { return b.length - a.length})
    let logPol = result.find((value)=>{
        return value === value.split('').reverse().join('') && value.length > 1
    })

    console.log(logPol);

Gratitude

Welcome to StackOverflow! Please explain your solution. – Arytenoid

1st reverse the string apply operation on reversed string. double for loop for iterating over the string. Inner loop makes substring from reversed like "ABCDE" "ABCD" "ABC" "AB" if match in main string keep the string into array. iterate loop for all the characters. Finally will get the matching string array. Arrange array based on length check the elements which are polindrome. – Gratitude

Answer 7

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("n"));

This will give wrong output so this condition need to be taken care where there is only one character.

Closed

Answer 8

  const str = "redder";
  let maxStr = "";

  for (let i = 0; i < str.length; i++) {
    let longStr = "";
    longStr += str[i];

    for (let j = i + 1; j < str.length; j++) {
      longStr += str[j];
      if (
        longStr.split("").reverse().join("") === longStr &&
        longStr.length > maxStr.length
      ) {
        maxStr = longStr;
      }
    }
  }

  console.log("maxStr:", maxStr);

Susi

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Witt

Answer 9

 public string LongestPalindrome(string s) {
       return LongestPalindromeSol(s, 0, s.Length-1);
 }
 public static string LongestPalindromeSol(string s1, int start, int end)
 {
        if (start > end)
        {
            return string.Empty;
        }
        if (start == end)
        {
            char ch = s1[start];
            string s = string.Empty;
            var res = s.Insert(0, ch.ToString());
            return res;
        }
        if (s1[start] == s1[end])
        {
            char ch = s1[start];
            var res = LongestPalindromeSol(s1, start + 1, end - 1);
            res = res.Insert(0, ch.ToString());
            res = res.Insert(res.Length, ch.ToString());
            return res;
        }
        else
        {
            var str1 = LongestPalindromeSol(s1, start, end - 1);
            var str2 = LongestPalindromeSol(s1, start, end - 1);
            if (str1.Length > str2.Length)
            {
                return str1;
            }
            else
            {
                return str2;
            }
        }
    }

Geld

Answer 10

This is in JS ES6. much simpler and works for almost all words .. Ive tried radar, redder, noon etc. 

const findPalindrome = (input) => {
  let temp = input.split('')
  let rev = temp.reverse().join('')

  if(input == rev){
    console.log('Palindrome', input.length)
  }
}
//i/p : redder
// "Palindrome" 6

Yl

it is simpler because you're not searching for a palindrome in the string but only if the string is a palindrome – Divorce

@Divorce mmm i don't follow, how does it know if its a valid word or not... would it just looking for similar chars following each other? that seem completely useless and invalid, as they would actually be none words. – Tarahtaran