Find Longest Palindromic Substring – SET 1

“Find Longest Palindromic Substring” is an important and one of the interview favourite problem of string data structure. Here, we are given a string and our task is to write a program to find the longest palindromic substring in the given string. 

Longest Palindromic Substring: Longest Palindromic Substring of the given string is a substring of the string which is also palindrome. We need to find the largest possible substring of such kind.

If there is no palindromic substring of length greater than 1 present in the string, simple return first character of the string.

Example:

INPUT:
abcba
OUTPUT:
Longest Palindromic Substring: abcba
Explanation:
“abcba” is itself palindromic string.
INPUT:
abcded
OUTPUT:
Longest Palindromic Substring: ded
Explanation:
“ded” is the longest substring in the string “abcded” which is palindromic.

In this post, we will discuss the brute-force approach to get the solution. The steps required to find longest palindromic substring are:

1. Initialize an empty resultant  string.
2. Generate all possible substring of the given string.
3. For every substring generated, check whether it is palindrome or not.
4. If it is palindrome, check its length with resultant string length.
5. If it’s greater, assign the resultant string with generated palindromic substring.

The time complexity of this solution is O(n⁴) for generating all substring and check palindrome.

C++ Program to Find Longest Palindromic Substring in a given string is as follows:

/* C++ Program to Find Longest Palindromic Substring in a given string */
#include<bits/stdc++.h>
using namespace std;
bool isPalindrome(string str)
{
    string temp = str;
    reverse(temp.begin(),temp.end());
    return (temp==str) ? true : false ;
}
void longestPalindrome(string str)
{
    // Single characterb is itself a palindrome
    string res = str.substr(0,1);
    //Generate all possible substrings of a given string
    for(int i = 0 ; i < str.length() ; i++)
    {
        for(int j = i ; j < str.length() ; j++)
        {
            string substring = "";
            for(int k = i ; k <= j ; k++)
            {
                substring = substring + str[k];
            }
            // check whether generated substring is palindrome or not
            bool checkPalindrome = isPalindrome(substring);
            // If palindrome, compare its length with resultant palindrome
            if(checkPalindrome)
            {
                if(substring.length() > res.length())
                res = substring;
            }
        }
    }
    cout<<"Longest Palindromic Substring: "<<res<<"\n";
}
int main()
{
    string str;
    
    /* Scan String */
    cout<<"Enter a string:\n";
    cin>>str;
    
    /* Function to find Longest Palindromic Substring */
    longestPalindrome(str);
}

OUTPUT:
Enter a string:
abcded
Longest Palindromic Substring: ded

Related Posts:

1. Program to check Anagram Strings.
2. Program to check whether two Strings are Rotation of each other or not.
3. Program to check Palindromic Anagram.
4. Program to print all the Palindromic Substring of the String.
5. Program to check Panagram String.
6. Program to find first non-repeating character of the String.
7. Program to Reverse a String.
8. Program to Count Number of Characters in a String.
9. Program to Count frequency of particular character of the String.
10. Program to Count Number of Vowels and Number of Consonants in a String.
11. Program to Check if String is alphabetic or numeric or alpha-numeric.
12. Program to copy one String to Another.
13. Program to Concatenate Two Strings.
14. Program to Check whether given String is Palindrome or not.
15. Program to convert lower-case alphabet to upper-case alphabet and vice-versa.
16. Program to count total number of words in a string.
17. Program to find smallest and largest word of the String.
18. Program to find Most Frequent Character of the String.
19. Program to Remove all the blank spaces from the String.
20. Program to check if String is isogram or not.