Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Longest Palindromic Substring

Last Updated on March 31, 2022 by Ria Pathak

CONCEPTS USED:

Recursion,Dynamic programming.

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

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. 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(n3)
Three nested loops are needed to find the longest palindromic substring in this approach, so the time complexity is O(n3)
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

int main()
{
int test;
scanf("%d",&test);

while(test--){

char a[1001];
scanf("%s",a);

int longestSubstring = 1, start=0, end = 0;

//Odd palindromic substrings
for(int i=1; i=0 && k longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}

//Even palindromic substring
for(int i=0; i=0 && k longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}

for(int i=start; i<=end; i++ )
printf("%c",a[i]);
printf("\n");

}
return 0;
}
#include
using namespace std;

int main()
{
int test;
cin>>test;

while(test--){

string a;
cin>>a;

int longestSubstring = 1, start=0, end = 0;

//Odd palindromic substrings
for(int i=1; i=0 && k longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}

//Even palindromic substrings
for(int i=0; i=0 && k longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}

for(int i=start; i<=end; i++ )
cout<

import java.util.*;
import java.io.*;
import java.lang.Math;

public class Main {
public static void main(String args[]) throws IOException {

Scanner sc= new Scanner(System.in);
int test = sc.nextInt();
while(test != 0){
String a = sc.next();

int longestSubstring = 1, start=0, end = 0;

//Odd palindromic substrings
for(int i=1; i=0 && k longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}

//Even palindromic substrings
for(int i=0; i=0 && k longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}

for(int i=start; i<=end; i++ )
System.out.print(a.charAt(i));

System.out.println();
test--;
}
}
}
for _ in range(int(input())):

a = list(input())
longestSubstring, start, end = 1, 0, 0

for i in range(1, len(a)):

j = i - 1
k = i

while( j >= 0 and k < len(a) and a[j] == a[k] ):

if( k - j + 1 > longestSubstring):

start = j
end = k
longestSubstring = k - j + 1

j -= 1
k += 1

for i in range(len(a)):

j = i - 1
k = i + 1

while( j >= 0 and k < len(a) and a[j] == a[k] ):

if( k - j + 1 > longestSubstring):

start = j
end = k
longestSubstring = k-j+1

j -= 1
k += 1

print(*a[start:end + 1], sep = "")

Space complexity: O(n2). It uses O(n2) space to store the table.

[forminator_quiz id="2335"]

This article tried to discuss Recursion, Dynamic programming. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion,Dynamic programming you can check out MYCODE | Competitive Programming.