Find longest palindrome in a string

Learn how to implement an algorithm to find the longest palindrome in a string.

Also known as longest palindromic substring or subsequence, we have to find the longest palindrome in the given string and return it. It is guaranteed that there will always be a palindrome because a single character is also a palindrome.

Example

Input:
"babad"
"cbbd"
"abcd"

Output:
"bab" or "aba"
"bb"
"a"

Finding longest palindrome in a string

The naive approach is to find all the substrings of the string which will run in O(n ^ 2) and then check if each substring is palindrome or not which will take additional O(n) so in total it will run on O(n ^ 3).

We can optimize it further to run it in O(n ^ 2) by checking if the substrings are palindrome or not in O(1).

By definition

Remember this definition because we are going to utilize this to check if string is palindrome in O(1).

Implementation

• We will use two nested loops to find all the substrings.
• For each sub string we will maintain it in two orders forward and reverse.
• In forward order we will add the next character after the current substring and in reverse order we will add the next character before the substring.
• If at any point the forward and reverse substring are same then it is a palindrome hence store it.
• Keep doing this for all the substring and return the longest palindrome.

Example of substring in forward and reverse order

Input:
"cbbd"

Forward:
"c"
"cb"
"cbb"
"cbbd"
"b"
"bb"  --- Match
"bbd"
"b"
"bd"
"d"

Reverse:
"c"
"bc"
"bbc"
"dbbc"
"b"
"bb"  --- Match
"dbb"
"b"
"db"
"d"

const longestPalindrome = (s) => {
    let max = Number.MIN_SAFE_INTEGER;
    let palindromeStr = "";
  
    for(let i = 0; i < s.length; i++){
        
        //If we have already have palindrome string
        //Greater than remaining string to be checked
        //Then break
        if(max > s.length - i){
            break;
        }
        
        let forward = "";
        let reverse = "";
      
        for(let j = i; j < s.length; j++){
            //Forward substring
            forward = forward + s[j];
          
            //Reverse substring
            reverse = s[j] + reverse;
          
            //If forward === reverse then it is a palindrome
            //So store if it is greater than max
            if(forward === reverse && max < forward.length){
                max = forward.length;
                palindromeStr = forward;
            }
        }
    }
  
    return palindromeStr;
};

Input:
console.log(longestPalindrome('abbc'));
console.log(longestPalindrome('babad'));
console.log(longestPalindrome('adccda'));

Output:
"bb"
"bab"
"adccda"

Time complexity: O(n ^ 2).
Space complexity: O(1).