Longest Palindromic Substring in C++

Program

#include 
#include 
#include 

using namespace std;

/**
 * Function to expand around the center and find the longest palindrome.
 * @param s The input string.
 * @param left The left index of the center.
 * @param right The right index of the center.
 * @return The longest palindromic substring centered at (left, right).
 */
string expandAroundCenter(const string& s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        --left;
        ++right;
    }
    return s.substr(left + 1, right - left - 1);
}

/**
 * Function to find the longest palindromic substring.
 * @param s The input string.
 * @return The longest palindromic substring in the input string.
 */
string longestPalindrome(const string& s) {
    if (s.empty()) return "";

    string longest;
    for (int i = 0; i < s.size(); ++i) { // Odd-length palindromes string oddPalindrome = expandAroundCenter(s, i, i); if (oddPalindrome.size() > longest.size()) {
            longest = oddPalindrome;
        }

        // Even-length palindromes
        string evenPalindrome = expandAroundCenter(s, i, i + 1);
        if (evenPalindrome.size() > longest.size()) {
            longest = evenPalindrome;
        }
    }
    return longest;
}

int main() {
    string input;
    cout << "Enter a string: "; cin >> input;

    string result = longestPalindrome(input);
    cout << "Longest palindromic substring: " << result << endl;

    return 0;
}
    

Explanation

The provided C++ program finds the longest palindromic substring in a given string using the “Expand Around Center” approach. This approach is efficient and works as follows:

1. Function: expandAroundCenter
   • This function expands around the center of a potential palindrome. It takes two indices, left and right, and keeps expanding outward as long as the characters at these indices are equal.
   • When expansion is no longer possible, it returns the longest palindromic substring found within the given indices.
2. Function: longestPalindrome
   • This function iterates through each character of the input string and treats it as the center of a palindrome.
   • It checks for both odd-length and even-length palindromes by calling expandAroundCenter with appropriate center indices.
   • It keeps track of the longest palindromic substring found and returns it as the result.
3. Main Function
   • It reads a string from the user, calls the longestPalindrome function, and prints the result.