ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

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

prodevelopertutorial July 21, 2018

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.

Longest Palindromic Substring In C++.

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

Longest Palindromic Substring In C++.

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.

Longest Palindromic Substring In C++.

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].

Longest Palindromic Substring In C++.

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:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io