# Longest Palindromic Substring

Strings

Medium

#### Problem Statement (Simplified):

Find the longest palindromic substring in a given string and print the substring.

See original problem statement here

#### Test Cases:

``````Input:
1
findnitianhere

Output:
indni

Explanation:
In 'findnitianhere', we have total 18 palindromic substrings that are 'f','i','n','d','ndn','indni','n','i','t','iti','i','a','n','h','e','r','ere' and 'e'. Here we can see 'indni' is the largest palindromic substing with length 5. So, 'indni' is our answer.``````

#### Solving Approach :

Bruteforce Approach:

1) We can find every possible substring of the given string and then find the largest string that is palindromic in them. We print such string.
2) This approach takes two loops for finding all substrings, and a loop for checking if the substring is palindrome or not for every possible substring found. Hence time complexity for this approach is `O(N^{3})`.
3) We can observe that length of the string goes from `1` to `10^{3}`, so this approach is inefficient for such string. We can solve this problem with a more efficient approach by referring online programming courses.

Efficient Approach:

1) Substring can be `odd` and `even` in length, so we find the longest substring in both length, and then print out the longest one.
2) For `odd` sized substrings, we start from a single pointer and expands both ways, and continue if both sides are equal. Once both characters i.e. in left and right are unequal or string ends, we compare the length of the current substring. If the length is higher than the current longest substring, we save the substring length and it's `start` and `end` index.
3) For `even` sized substrings, we initialize with two pointers i.e. `left` and `right` and expand them on both sides, and repeat the same process as in case of `odd`.
4) We perform this iteration for every index of the substring.

## Example

• Let's assume string `S` is `bbbbbabbb`. So we iterate over string character by character and check for both `odd` sized and `even` sized palindromes having current character as middle element.

Odd sized Palindromes : We use a pointer start, we'll iterate towards both end of start and will continue until characters on both sides does'nt match

> For i=1 : > From above image, we can see that palindromic substring found is `'bbb'` with length `3`.
>
> For i=2 : > From above image, we can see that palindromic substring found is `'bbbbb'` with length `5`.
>
> For i=3 : > From above image, we can see that palindromic substring found is `'bbb'` with length `3`.
>
> For i=4 : > From above image, we can see that palindromic substring found is `'b'` with length `1`.
>
> For i=5 : > From above image, we can see that palindromic substring found is `'bbbabbb'` with length `7`.
>
> For i=6 : > From above image, we can see that palindromic substring found is `'b'` with length `1`.
>
> For i=7 > From above image, we can see that palindromic substring found is `'bbb'` with length `3`.
>
Here we can see we find largest palindromic substring with length `7` at starting at index `2` and ending at index `8` having middle element at index `i=5`.

Even sized Palindromes : We use two pointers i.e. i and j for it, we'll iterate towards both ends of i and j, we will continue until characters on both sides does'nt match
>
> > From above image, we can see that palindromic substring found is `'bbbb'` with length `4`.
>
> > From above image, we can see that palindromic substring found is `'bbbb'` with length `4`.
>
> > From above image, we can see that palindromic substring found is `'bb'` with length `2`.
>
> > From above image, we can see that no palindromic substring is found.
>
> > From above image, we can see that no palindromic substring is found.
>
> > From above image, we can see that palindromic substring found is `'bb'` with length `2`.
>
> > From above image, we can see that palindromic substring found is `'bb'` with length `2`.

Here we can see we find largest palindromic substring with length `4` which is smaller than the largest palindromic string found in `odd` section. So substring found in odd section is our final answer.

So our longest palindromic substring starts at index `2` and ends at `8` with size `7` and substring is `'bbbabbb'`

## Solutions

```#include <stdio.h>

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

while(test--){

char a;
scanf("%s",a);

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

//Odd palindromic substrings
for(int i=1; i<strlen(a); i++){
int j= i-1, k=i;
while( j>=0 && k<strlen(a) && a[j]==a[k] ){
if( k-j+1 > longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}

//Even palindromic substring
for(int i=0; i<strlen(a); i++){
int j= i-1, k=i+1;
while( j>=0 && k<strlen(a) && a[j]==a[k] ){
if( k-j+1 > 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 <bits/stdc++.h>
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<a.length(); i++){
int j= i-1, k=i;
while( j>=0 && k<a.length() && a[j]==a[k] ){
if( k-j+1 > longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}

//Even palindromic substrings
for(int i=0; i<a.length(); i++){
int j= i-1, k=i+1;
while( j>=0 && k<a.length() && a[j]==a[k] ){
if( k-j+1 > longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}

for(int i=start; i<=end; i++ )
cout<<a[i];
cout<<endl;

}
return 0;
}
```
```
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<a.length(); i++){
int j= i-1, k=i;
while( j>=0 && k<a.length() && a.charAt(j)==a.charAt(k) ){
if( k-j+1 > longestSubstring){
start = j;
end = k;
longestSubstring = k-j+1;
}
j--;
k++;
}
}

//Even palindromic substrings
for(int i=0; i<a.length(); i++){
int j= i-1, k=i+1;
while( j>=0 && k<a.length() && a.charAt(j)==a.charAt(k) ){
if( k-j+1 > 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--;
}
}
}
```

Space Complexity of this approach would be `O(1).`