Given a string find the longest Palindromic Substring with detailed explanation and solution in C++.

A palindromic string will give the same string when reading reverse.

Example:

“aba” reverse is “aba” hence is a palindromic string.

Input: ashdkabajjseiw      

Output: aba

There are 3 approaches, in this tutorial, we shall discuss 2 methods

1. Brute force approach. Time Complexity O(n ^ 3)
2. Dynamic Programming. Time Complexity O(n ^ 2)m space complexity O(n ^ 2)
3. Manacher’s algorithm, discussed in the separate post.

Brute force approach:

Time complexity: O(n^3)

In this approach, we take all possible substring in the given string and then take their reverse. And we shall match the reverse with the given substring. Hence checking the longest substring.

Example:

Input String “aba”

Possible Substring               Reverse of substring

a                                                a
ab                                               ba
aba                                              aba
ba                                               ba
b                                                b
a                                                a

Hence the output will be “aba” as it is the longest palindromic substring.

For this approach, we take 2 loops, outer for loop, and inner for loop.

Then call the “check_palindrome” function to display the longest palindrome.

Brute force Solution in C++ language:

#include<iostream>
#include<string>
using namespace std;

bool isPalindrome(string str)
{
    if (str.length() == 0)
        return false;

    if (str.length() == 1)
        return true;

    int halflen = str.length() / 2;
    int len = str.length() - 1;

    for (int i = 0; i < halflen; i++)
    {
        if (str[i] != str[len])
        {
            return false;
        }
        len--;
    }
    return true;
}

string bruteForceGetLongestPalindrome(string input_str)
{
    int palindromeLength = 0;
    string resultstring = "";

    //loop to get substring 

    for (int i = 0; i < input_str.length(); ++i)
    {
        string subString = "";
        subString += input_str[i];

        for (int j = i + 1 ; j < input_str.length(); j++)
        {
            subString += input_str[j];

            //check if the substring is a palindrome
            if( isPalindrome (subString) ) 
            {
                if (palindromeLength < subString.length())
                {
                    palindromeLength = subString.length();
                    resultstring += subString;
                }
            }

        }

    }
    return resultstring;
}

int main()
{
    string resultstring = bruteForceGetLongestPalindrome("ashdkabajjseiw");
    cout<<"The longest substring is " << resultstring <<endl;

}

output:

The longest substring is aba

Dynamic programming approach:

First, what is dynamic programming?

Dynamic programming is dividing a complex problem into smaller subproblems and solving those subproblems and storing the result of those subproblems in the memory like a table or an array and come back to check those results whenever needed.

In our solution approach, we use a 2D Boolean array to store the results.

Let us take an example

“abaab” is the string, we need to get the longest palindromic substring.

In pass 1, length =1 here i = j
    Hence substring of [0][0], [1][1], [2][2], [3][3], [4][4] are true. As shown in figure below.

In pass 2, length = 2 here j = i+1
    Hence the truth value of the substrings [0][1], [1][2], [2][3], [3][4] are updated if both the values are same. As shown in figure 2

For a string to be considered as a palindrome, we use the below formula:

If (str [i] == str[j] and table_value [i +1] and [j -1] is true) then the string is a palindrome.

In pass 3, length = 3 here j = i + 2
    Hence we look at the substrings [0] [2], [1] [3], [2] [4]. As we can see from the table below, “aba” is a palindromic substring we have got.

For a string to be palindrome we need to check if the first and last character is same. Because the middle character value has already been calculated and stored in the array.

In pass 4, length 4 here j = I + 3
    Hence the substrings will be [0][3], [1][4].

Here we get the substring “baab”, here have to calculate the value of [1] [4], all other values have already been filled. Hence the solution.

Here the time complexity is O (n ^2)

Space complexity is also O(n ^2)

The solution in c++ for Dynamic Programming

#include<iostream>
#include<string>
using namespace std;

string DynamicProgrammingGetLongestPalindrome(string input_str)
{
    if(input_str.length()<=1)
        return input_str;
    int string_length = input_str.length();
    int palindromeLength = 0;
    bool bArray[string_length] [string_length];

    string resultstring = "";

    for (int current_length = 0; current_length < string_length; current_length++)
    {
        for (int i = 0; i < string_length -1 ; i++)
        {
            int j = i + current_length;

                if(input_str[i]==input_str[j] && (j-i<=2 || bArray[i+1][j-1]))
                {
                    bArray[i][j]=true;
 
                    if(j-i+1>palindromeLength)
                    {
                       palindromeLength = j-i+1; 
                       resultstring = input_str.substr(i, j+1);
                    }
            }
        }
    }
    return resultstring;


}


int main()
{
    string resultstring = DynamicProgrammingGetLongestPalindrome("xaabbaa");
    cout<<"The longest substring is " << resultstring <<endl;

}

Output:

The longest substring is aabbaa

List Of Tutorials available in this website: