Finding the Longest Palindromic Substring

Home

Community

Blog Posts

Programming

Tech Topics

Explore

Find Jobs

Finding the Longest Palindromic Substring

Asked 10 months ago

1Comments

42 Views

A palindromic substring is a sequence of characters that reads the same forward as backward. For example, "mom", "lool", "noon", etc. Given a string, the task is to find the longest palindromic substring within it.

Example

For the string "babad", the longest palindromic substring is "bab" or "aba".

Approach

To solve this problem, we need to follow these steps:

Find all substrings of the given string
Check which substrings are palindromic
Return the longest (maximum) palindromic substring

Step-by-step Explanation

isPalindrome() Function

This function checks if a given substring is a palindrome or not.

It takes a string s and two indices start and end as parameters.
It uses a while loop to compare characters from the start and end, moving towards the center.
If at any point the characters are not equal, the function returns false.
If the loop completes without finding any mismatch, the function returns true.

longestPalindromicSubstring() Function

This function initializes an empty string ans to store the longest palindromic substring found.
It uses two nested loops to iterate over all possible substrings in the input string s.
For each substring, it calls the isPalindrome function to check if it's a palindrome.
If it is, the substring is compared with the current longest palindromic substring (ans), and if it's longer, it replaces the current ans.
After both loops complete, the function returns the longest palindromic substring found.

Main Function

In the main function, we've defined a string s = "babad" as an example input. We then call the longestPalindromicSubstring function with this input string, and the result is printed as the output.

#include <iostream>
#include <string>

using namespace std;

// Function to check if a given substring is a palindrome
bool isPalindrome(const string& s, int start, int end) {
   while (start < end) {
       if (s[start] != s[end]) {
           return false;
       }
       start++, end--;
   }
   return true;
}

// Function to find the longest palindromic substring
string longestPalindromicSubstring(const string& s) {
   string ans = "";
   for (int i = 0; i < s.length(); i++) {
       for (int j = i; j < s.length(); j++) {
           string t = s.substr(i, j - i + 1);
           if (isPalindrome(s, i, j) && t.length() > ans.length()) {
               ans = t;
           }
       }
   }
   return ans;
}

int main() {
   string s = "babad";
   string substring = longestPalindromicSubstring(s);
   cout << "Longest Palindromic Substring is: " << substring << endl;
   return 0;
}

This is a brute force approach with a time complexity of O(n^3), where n is the length of the input string. While it works correctly, it's inefficient for large input strings. The optimal solution can be obtained using dynamic programming, which has a time complexity of O(n^2). However, the dynamic programming approach is more complex and may be challenging for beginners to understand initially

Try yourself in LEETCODE : https://leetcode.com/problems/longest-palindromic-substring/description/

cpp

Strings

Programming

medium

1 Responses

ADil Sarfraz

commented 10 months ago

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string longestPalindromicSubstring(const string& s) {
    int n = s.length();
    if (n == 0) return "";
    
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int start = 0, maxLength = 1;

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

    // Check for substrings of length 2
    for (int i = 0; i < n - 1; ++i) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }

    // Check for substrings of length greater than 2
    for (int len = 3; len <= n; ++len) {
        for (int i = 0; i < n - len + 1; ++i) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                start = i;
                maxLength = len;
            }
        }
    }

    return s.substr(start, maxLength);
}

int main() {
    string s = "babad";
    string substring = longestPalindromicSubstring(s);
    cout << "Longest Palindromic Substring is: " << substring << endl;
    return 0;
}

Finding the Longest Palindromic Substring

Write your comment here !

1 Responses