Coding Interview: 2 Solutions to the Longest Palindromic Substring

Prompt

Leetcode link: https://leetcode.com/problems/longest-palindromic-substring/description/

Solution 1 (not preferred):

This is the brute Force method. It is O(n³) because it’s O(n²) with the nested for loop and each substring needs to be checked if it is a palindrome.

Complexity: O(n³)

//Brute Force method
//Complexity: O(n^3) because O(n^2) with the nested for loop and each substring needs to be checked if it is a palindrome
var longestPalindrome = function(s) {
    let current = "";

    for (let i=0; i<s.length; i++){
        for (let j=i+1; j<s.length; j++){
            let ss = s.substring(i,j);

            if (isPalindrome(ss)){
                if (ss.length > current.length){
                    current = ss;
                }
            }
        }
    }
    return current;
};

function isPalindrome(s){
    let reverse = s.split("").reverse().join("");
    
    if (s == reverse){
        return true;
    } else {
        return false;
    }
}

Solution 2 (preferred)

In this method, there is no need to check every possibly substring like the solution above. At each index, we check to see if the positions to the left and right or the…