Longest Palindromic Substring

Table of Contents

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

Try It

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

Try It