Longest Palindromic Substring

CONCEPTS USED:

Recursion,Dynamic programming.

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT$($SIMPLIFIED$)$:

You are given a string str, find the longest palindromic substring in str.
Longest Palindromic Substring of string str:LPS[i...j], ​where 0<=i<=j< len(LPS)
Palindrome string:LPS ​is palindrome if reverse(LPS) =LPS
If multiple LPS is the same then return the Longest Palindromic Substring which occurs first ( with the least starting index ).

See original problem statement here

For Example :

Input
3
aaa
bbabb
baa

Output
aaa
bbabb
aa

SOLVING APPROACH:

Brute Force:

The simple approach is to check each substring whether the substring is a palindrome or not with the help of some websites to learn coding. To do this first, run three nested loops, the outer two loops pick all substrings one by one by fixing the corner characters, the inner loop checks whether the picked substring is palindrome or not.

Time complexity: O(n^3).
Three nested loops are needed to find the longest palindromic substring in this approach, so the time complexity is O(n^3).
Auxiliary complexity: O(1).
As no extra space is needed.

OPTIMIZATION:

To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes. Consider the case "ababa". If we already knew that "bab" is a palindrome, it is obvious that "ababa" must be a palindrome since the two left and right end letters are the same.


P(i,j) = {true,}if the substring Si …Sj is a palindrome;
        {false,}otherwise

Therefore,
P(i, j) =(P(i+1,j−1) and Si==Sj)

The base cases are:
P(i, i) = true
P(i, i+1) = (Si==Si+1 )

This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on...

SOLUTIONS:

#include <stdio.h>

int main()
{
  //write your code here
  int t;scanf("%d",&t);
  while(t--)
  {
    char s[1001];scanf("%s",s);
    int n=strlen(s);
    int dp[n][n];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++)
    { 
        dp[i][i]=1;
    }
    int ans=1,st=0;
    for(int i=0;i<n-1;i++)
    {
      if(s[i]==s[i+1])
      {
        dp[i][i+1]=1;
        if(ans<2)
        {ans=2;
          st=i;
        }
      }
    }
    for(int i=3;i<=n;i++)
    {
      for(int j=0;j<n-i+1;j++)
      {
        int k=j+i-1;
        if(s[j]==s[k])
        {
          if(dp[j+1][k-1]==1)
          {dp[j][k]=1;
          if(ans<i)
          ans=i;
            st=j;
          }
        }
      }
    }
    for(int i=st;i<st+ans;i++)
    printf("%c",s[i]);
    printf("\n");
  }
  return 0;
}
#include <bits/stdc++.h>
using namespace std;

int main()
{
  //write your code here
  int t;cin>>t;
  while(t--)
  {
    string s;cin>>s;
    int n=s.length();
    int dp[n][n];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++)
    { 
        dp[i][i]=1;
    }
    int ans=1,st=0;
    for(int i=0;i<n-1;i++)
    {
      if(s[i]==s[i+1])
      {
        dp[i][i+1]=1;
        if(ans<2)
        {ans=2;
          st=i;
        }
      }
    }
    for(int i=3;i<=n;i++)
    {
      for(int j=0;j<n-i+1;j++)
      {
        int k=j+i-1;
        if(s[j]==s[k])
        {
          if(dp[j+1][k-1]==1)
          {dp[j][k]=1;
          if(ans<i)
          ans=i;
            st=j;
          }
        }
      }
    }
    for(int i=st;i<st+ans;i++)
    cout<<s[i];
    cout<<"\n";
  }
  return 0;
}
import java.util.*;

class solution{
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0){
             String s=sc.next();
             int n=s.length();
             int dp[][]=new int[n][n];

            //  for(int i=0;i<n;i++){
            //      for(int j=0;j<n;j++){
            //          dp[i][j]=0;
            //      }
            //  }

         for(int i=0;i<n;i++)
         { 
         dp[i][i]=1;
         }
         int ans=1,st=0;

         for(int i=0;i<n-1;i++)
         {
         if(s.charAt(i)==s.charAt(i+1))
         {
         dp[i][i+1]=1;
         if(ans<2)
        {
          ans=2;
          st=i;
        }
      }
    }

    for(int i=3;i<=n;i++)
    {
      for(int j=0;j<n-i+1;j++)
      {
        int k=j+i-1;
        if(s.charAt(j)==s.charAt(k))
        {
          if(dp[j+1][k-1]==1)
          {
          dp[j][k]=1;
          if(ans<i)
            ans=i;
            st=j;
          }
        }
      }
    }
    for(int i=st;i<st+ans;i++)
    System.out.print(s.charAt(i));

    System.out.println();
   }
  }
}

Space complexity : O(n^2). It uses O(n^2) space to store the table.

Previous post Min Query
Next post Play Games 3

Leave a Reply

Your email address will not be published. Required fields are marked *