Skip to main content

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

Comments

Popular posts from this blog

Python - Mathematical Functions - Hexadecimal, Binary, Exponential, Absolute, Round

🐍 Some mathematical functions are in-built in python. Here are some of them. Convert Decimal to Hexadecimal hex(246) Output: '0xf6' hex(512) Output: '0x200' 0x is prefix to all hexadecimal numbers in output. The number after 0x is the hexadecimal value. Convert Decimal to Binary bin(1234) Output: '0b10011010010' bin(246) Output: '0b11110110' bin(512) Output: '0b1000000000' Exponential Function pow() function is similar to num1**num2, but it comes useful when you want to execute (num1**num2)%num3. Passing three arguments to pow(), does this. pow(3,4) Output: 81 This works just like 3**4 pow(3,4,5) Output: 1 But this, works equivalent to (3**4)%5. Either of the two ways can be used. At this point I feel (3**4)%5 is better, as anybody reading the code will understand what is being done immediately. While with pow(2,3,4), the person may have to refer to documentation to understand how this function works. Absolute Value The function abs() is used ...

Two Ways of rendering in React Examples

Two Ways of rendering in React Examples 1 - Render twice HTML < div id = "p1" ></ div > < div id = "p2" ></ div > CSS . person { display : inline - block ; margin : 10px ; border : 1px solid # eee ; box - shadow : 0 2px 2px # ccc ; } JAVASCRIPT (Babel) function Person ( props ) { return ( < div className = ' person "> < h1 >{ props . name }</ h1 > < p > Age :{ props . age }</ p > </ div > ); } ReactDOM . render (< Person name = "VK" age = "29" />, document . querySselector ( '#p1' )); ReactDOM . render (< Person name = "HK" age = "28" />, document . querySselector ( '#p2' )); 2 Render all at once HTML < div id = "app" ></ div > CSS . person { display : inline - block ; margin : 1...

Binary Tree Traversal in Python - In Order, Pre Order, Post Order

Binary Tree Traversal in Python - In Order, Pre Order, Post Order Run the code here to see output:  https://repl.it/@VinitKhandelwal/iterative-traversal-of-binary-tree # Node Class to Create Object of Nodes class Node (): def __init__ ( self , value , left= None , right= None ): self .value = value self .left = left self .right = right # Creation of a Binary Tree class BinaryTree (): def __init__ ( self , mylist ): self .mylist = mylist self .root=Node ( None ) for value in self .mylist : self .curr= self .root self ._add ( value ) def _add ( self , value ): if self .curr.value == None : self .curr.value = value else : if self .curr.value > value : if self .curr.left == None : self .curr.left = Node ( value ) else : self .curr = self .curr.left self ._add ( value ) else : if self...