Longest Palindromic substring Problem

Given a string S which contains various types of Characters finds the longest palindromic substring.

what is a Palindromic String?

A String is said to be a Palindromic substring if we move from the beginning of the string and end of the string then we will get symmetric characters.

In another word, a String is a palindrome if we reverse it then we will get the same string.

Example:- ABCCBA

This is a palindromic String because if we move from the beginning of ABCCBA to and the end of it we will get the same character.

This is one of the favorite questions for interviewers. This problem is based On Manachers's Algorithm. The interviewer Might ask you about the longest palindromic subsequence problem so you should know Manachers's Algorithm to explain it.

Here is the Brute force approach to find the longest palindromic substring in Java. You can implement it in Your Corresponding programming language.

Here in the above question, we have to find the Longest Palindromic Substring question from LeetCode or GeeksforGeek

class Solution {
 public static boolean ispallindrome(String k)
    {
   char[] s = k.toCharArray();
      
   for(int i=0;i<s.length;i++)
        {
   if(s[i]!=s[s.length-i-1]) return false;
        }
     return true;
    }
 public String longestPalindrome(String s) {
          int y=0;
        String m=null;
   for(int i=0;i<s.length();i++)
        {
      if(s.substring(i).length()<y)
            {
                return m;
            }
 for(int j=i;j<s.length();j++)   
        {
            
            {
   if(ispallindrome(s.substring(i,j+1)))
            {
   if(s.substring(i,j+1).length()>y) 
               {
    y=s.substring(i,j+1).length();
    m=s.substring(i,j+1);
               }
            }
            
        }
            
            
        }}
        
        return m;
        
    }
}

This code will smoothly Run for small String Values. but it will give Time limit Exceeded error for Long String. so we need an optimized solution for finding the longest palindromic substring.

Optimized code to find Longest Palindromic String

class Solution {
  public String longestPalindrome(String s) {
   int start = 0, end = 0;
  for (int i = 0; i < s.length(); i++) {
    int len1 = expand(s, i, i);
    int len2 = expand(s, i, i + 1);
   if ( Math.max(len1, len2) > end - start) {
  start = i - (( Math.max(len1, len2) - 1)>>1);
  end = i + ( Math.max(len1, len2)>>1);
        }
    }
 return s.substring(start, end + 1);
}

private int expand(String s, int left, int right) {
    int L = left, R = right;
  while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}
}