Longest palindrome program

Question

I am going through this longest palindrome program:

   public static String longestPalindrome(String s) {
        if(s==null || s.length()<=1)
            return s;

        int len = s.length();
        int maxLen = 1;
        boolean [][] dp = new boolean[len][len];

        String longest = null;
        for(int k=0; k<s.length(); k++){
            for(int i=0; i<len-k; i++){
                int j = i+k;
                if(s.charAt(i)==s.charAt(j) && (j-i<=2||dp[i+1][j-1])){
                    dp[i][j]=true;

                    if(j-i+1>maxLen){
                       maxLen = j-i+1; 
                       longest = s.substring(i, j+1);
                    }
                }
            }
        }

        return longest;
    }

I ran this program in debug mode in my eclipse multiple times, but it is not clear for me how this program is able to get the longest palidrome value.

How the boolean array is used, how the variable j is used, mainly what is the use of this condition j-i<=2||dp[i+1][j-1]

The link says the space complexity is O(n^2), which part of the program indicates this space complexity.

Answer 1

Simple solution to find longest palindromic substring

let userInput = "FRACECARID";
let reversedString, originalString, longestPalindrome;
let palindromeArray = [];
for(let i = 0; i < userInput.length - 1; i++){
    for(let j = i + 2; j < userInput.length + 1; j++){
        originalString = userInput.substring(i, j);
        reversedString = originalString.split("").reverse().join("");
        if(originalString == reversedString){
            palindromeArray.push({x: originalString.length, y: originalString});
        }
    }
}
palindromeArray.sort(compareX); //sorting in descending order based on length of the palindrome
longestPalindrome = palindromeArray[0].y;
console.log("Longest Palindrome: ", longestPalindrome);
function compareX(a, b){
    return b.x - a.x;
}

Answer 2

Find out the longest Palindrome in a string using Javascript

Optimal Solution

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
}

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

Example Input

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

Output

bababababababababababab
bababababababababababab
bababababababababababab
bababababababababababab

Try these solutions on Leetcode: https://leetcode.com/problems/longest-palindromic-substring

Answer 3

It is a Dynamic Program approach. Where you start from one letter string (which is a palindrome by default) and gradually increase the number of letters in a string.

For that they are using two dimensional array,

    /*
 *      B  A  N  A  N  A
 *     ------------------
 *  B | T  F  F  F  F  F
 *  A |    T  F  T  F  T
 *  N |       T  F  T  F
 *  A |          T  F  T 
 *  N |             T  F
 *  A |                T
 * */

thus space complexity n^2.

For any [i][j] cell you need to check [i+1][j-1] cell in order to find out that whether the substring before adding this letter was palindrome or not.

Below link has a very articulate video It is using similar approach.
http://www.ideserve.co.in/learn/longest-palindromic-substring