Header Ads Widget

Ticker

6/recent/ticker-posts

Longest Palindromic substring

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.

  

Longest Palindromic substring


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

Solve Longest Palindromic Substring Problem at LeetCode

Solve Longest Palindromic Substring Problem at GeeksForGeek

Solve Longest Palindromic Subsequence Problem at hackerrank

In this code, we are using Manachers's Algorithm to make our code less complex and highly efficient for large values of string.
Get more solutions to competitive programming questions only at courpedia.


:- You Might Like  -: