5 Longest Palindromic Substring — Leetcode Problem Javascript Solutions

5. Longest Palindromic Substring

Medium

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"

Find out the longest Palindrome in a string using Javascript

Fairly optimal solution

const longestPalindrome = str => {
  let isPalindrome = false;
  let test;
  for (let i = str.length; i > 0; i--) {
    for (let j = 0; j <= str.length - i; j++) {
      isPalindrome = true;
      test = str.slice(j, j+i);
      for (let k = 0; k < Math.floor(test.length/2); k++) {
        if (test[k] !== test[test.length-1-k]) {
          isPalindrome = false;
          break;
        }
      }
      if (isPalindrome) {
        return test;
      }
    }
  }
  return "";
}

Brute force sort of solution

const longestPalindrome1 = str => {
  let longestPalindrome = "";
  for (let i = 0; i < str.length; i++) {
    for (let j = str.length ; j > i; j--) {
      const test = str.slice(i,j);
      let isPalindrome = true;
      for (let k = 0; k < test.length/2; k++) {
        if (test[k] !== test[test.length - 1 - k]) {
          isPalindrome = false;
        }
      }
      if (isPalindrome && test.length > longestPalindrome.length) {
        longestPalindrome = test;
        break;
      }
    }
  }
  return longestPalindrome;
}

Recursive Solution

const longestPalindrome2 = str => {
  if (str.length > 1){
    let [palindrome1, palindrome2] = [str, str];
    for (let i=0;i<Math.floor(str.length/2);i++) {
      if(str[i]!==str[str.length-i-1]) {
        palindrome1 = longestPalindrome(str.slice(0, str.length-1));
        palindrome2 = longestPalindrome(str.slice(1, str.length));
        break;
      }
    }
    return palindrome2.length > palindrome1.length ? palindrome2 : palindrome1;
  } else {
    return str;
  }
}

Fast Javascript Solution to finding the longest palindrome in a string:

const lpal = str => {
  let lpal = ""; // to store longest palindrome encountered
  let pal = ""; // to store new palindromes found
  let left; // to iterate through left side indices of the character considered to be center of palindrome
  let right; // to iterate through left side indices of the character considered to be center of palindrome
  let j; // to iterate through all characters and considering each to be center of palindrome
  for (let i=0; i<str.length; i++) { // run through all characters considering them center of palindrome
    pal = str[i]; // initializing current palindrome
    j = i; // setting j as index at the center of palindorme
    left = j-1; // taking left index of j
    right = j+1; // taking right index of j
    while (str[j] === str[right]) { // while right elementis same as center element
      pal = pal + str[right]; // then add right to pal
      right++; // increase right by one
    }
    while (left >= 0 && right < str.length) { // while left and right indices exist
      if(str[left] === str[right]) { // if left value is equal to right value
        pal = str[left] + pal + str[right]; // add in front and back of pal
      } else { // if left value is NOT equal to right value
        break; // break out of while
      }
      left--; // move left index by one
      right++; // move right index by one
    }
    if(pal.length > lpal.length) { // if this pal longer than longest pal 
      lpal = pal; // set longest pal to be this pal
    }
  }
  return lpal; // return longest pal
}

Example Input

console.log(longestPalindrome2("babababababababababababa"));
console.log(longestPalindrome1("babababababababababababa"));
console.log(longestPalindrome("babababababababababababa"));
console.log(lpal("gerngehgbrgregbeuhgurhuygbhsbjsrhfesasdfffdsajkjsrngkjbsrjgrsbjvhbvhbvhsbrfhrsbfsuhbvsuhbvhvbksbrkvkjb"));

Output

bababababababababababab
bababababababababababab
bababababababababababab
asdfffdsa

Run the code here: https://repl.it/@VinitKhandelwal/longest-palindrome-javascript