Home » Technical Interview Questions » String Interview Questions » Longest Palindromic Substring

# Longest Palindromic Substring

## Given a string, write a function that will find the longest palindromic substring

### Example

INPUT

s = “ebcdcbn”

OUTPUT

“bcdcb” is the longest palindromic substring

### Method 1(Brute Force) :

In this method we will pick all the substrings and check whether the substring is palindrom or not

Time Complexity: O(n^3)

## Algorithm

1. Simply run three loops

2. In the outer loop pick all substrings one by one by fixing the corner elements

3. In the inner loop check whether the picked substring is palindrome or not

### Method 2(Dynamic Programming) :

In this method the main idea is to store the results of subproblems

Time Complexity : O(n^2)

Space Complexity : O(n^2)

## Algorithm

1. Create a two diemensional Boolean array, ie table[n][n], where table[i][j] is true if the string from  i index to j index is a palindrome

2. All the substrings of length 1 are palindromes, so make table[i][i] TRUE

3. For all the substrings of length 2, if the first and second character are same then it is a palindrome ie, if s[i] = s[i+1] make table[i][i+1] = true

4. Now, check for substrings having length more than 2.
The Condiiton is, table[i][j] is true if the value of table[i+1][j-1] is true and s[i] is same as s[j] ie, for above example “bcdcb” is a palindorme because “cdc” is a palindrome and ‘b’ == ‘b’ .

## C++ Program

```#include <bits/stdc++.h>
using namespace std;

//It will take the string and prints the longest palindromic substring
//and its length
void printLPSS( char *s )
{
//finding the length of given string
int n = strlen(s);

//Table table[i][j] is true if the string from  i index to j index is a palindrome
bool table[n][n];
//Initializing all contents of the table to 0
memset(table, 0, sizeof(table));

// All substrings of length 1 are palindromes
int maxLength = 1;
for (int i = 0; i < n; ++i)
table[i][i] = true;

// check for sub-string of length 2.
int start = 0;
for (int i = 0; i < n-1; ++i)
{
if (s[i] == s[i+1])
{
table[i][i+1] = true;
start = i;
maxLength = 2;
}
}

// Check for lengths greater than 2. k is length
// of substring
for (int k = 3; k <= n; ++k)
{
// Fix the starting index
for (int i = 0; i < n-k+1 ; ++i)
{
// Get the ending index of substring from
// starting index i and length k
int j = i + k - 1;

// checking for sub-string from ith index to
// jth index iff s[i+1] to s[j-1] is a
// palindrome
if (table[i+1][j-1] && s[i] == s[j])
{
table[i][j] = true;

if (k > maxLength)
{
start = i;
maxLength = k;
}
}
}
}
//Printing the longets palindromic substring
int end = start + maxLength - 1;
cout<<"Longest palindrome substring is ";
for( int i = start; i <= end; ++i )
{
cout<<s[i];
}
cout<<endl;
//Length of the above longest palindromic substring
cout<<maxLength<<endl;
}

int main()
{
char s[] = "ebcdcbn";
printLPSS(s);
return 0;
}```

### Method 3

In this method the main idea is to generate all even length and odd length palindromes and keep track of longest palindrome

Time Complexity: O(n^2)
Space Complexity: O(1)

## Algorithm

Traverse through the given string

1. For the odd length palindrome, Fix the centre and expand in both directions for longer palindromes
Example for odd length palindorme, s = “ebcdcbn”

Traverse the string with low = i-1 and high = i+1, where initial i =1
At some point we stop at low = ‘c’ and high = ‘c’, low = high. Expand on both directions
Now, low = ‘b’ and high = ‘b’. low = high
Therfore the longest palindrome is “bcdcb”

2. For the even length palindrome, there will be no centre and will expand on both directions for longer palindromes
Example for even length palindrome, s = “ebccbn”

Traverse the string with low = i-1 and high = i
At some point we stop at low = ‘c’ and high = ‘c’, low = high. Expand on both directions
Now, low = ‘b’ and high = ‘b’. low = high
Therfore the longest palindrome is “bccb”

## C++ Program

```#include <bits/stdc++.h>
using namespace std;

//It will take the string and prints the longest palindromic substring
//and its length
void printLPSS(char *s)
{
int maxLength = 1;  // The result (length of LPS)

int start = 0;
int n = strlen(s);

int low, high;

// One by one consider every character as center point of
// even and length palindromes
for (int i = 1; i < n; ++i)
{
// Find the longest odd length palindrome with center
// point as i
low = i - 1;
high = i + 1;
while (low >= 0 && high < n && s[low] == s[high])
{
if (high - low + 1 > maxLength)
{
start = low;
maxLength = high - low + 1;
}
--low;
++high;
}

// Find the longest even length palindrome with no centre point
low = i - 1;
high = i;
while (low >= 0 && high < n && s[low] == s[high])
{
if (high - low + 1 > maxLength)
{
start = low;
maxLength = high - low + 1;
}
--low;
++high;
}
}
//Printing the longest palindromic substring
int end = start + maxLength - 1;
cout<<"Longest palindrome substring is ";
for( int i = start; i <= end; ++i )
{
cout<<s[i];
}
cout<<endl;
//Length of the above longest palindromic substring
cout<<maxLength<<endl;
}

int main()
{
char s[] = "ebccbn";
printLPSS(s);
return 0;
}```