Longest Palindromic Substring - C++ Solution

1. Introduction

In this post, we will dive into a classic problem in string processing - finding the longest palindromic substring within a given string. A palindrome is a string that reads the same forwards and backwards, and identifying such sequences has applications in various fields including genetics, text processing, and computer science puzzles.

Problem

Given a string, the task is to find the longest contiguous substring that is also a palindrome. If there are multiple palindromic substrings of the same maximum length, the one appearing first in the string should be returned.

2. Solution Steps

1. Initialize variables to keep track of the longest palindrome found (longestPalindrome).

2. Iterate through each character in the string.

3. For each character, expand around its center (considering both odd and even length palindromes) and check for the longest palindrome.

4. Update the longestPalindrome if a longer palindrome is found.

5. Return the longest palindrome after completing the iteration.

3. Code Program

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

// Function to expand around the center of the palindrome
string expandAroundCenter(const string& s, int left, int right) {
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        left--;
        right++;
    }
    // Return the longest palindrome found in this expansion
    return s.substr(left + 1, right - left - 1);
}

// Function to find the longest palindromic substring
string longestPalindromicSubstring(const string& s) {
    string longestPalindrome = "";

    for (int i = 0; i < s.length(); i++) {
        // Check for odd length palindrome
        string oddPalindrome = expandAroundCenter(s, i, i);
        if (oddPalindrome.length() > longestPalindrome.length()) {
            longestPalindrome = oddPalindrome;
        }

        // Check for even length palindrome
        string evenPalindrome = expandAroundCenter(s, i, i + 1);
        if (evenPalindrome.length() > longestPalindrome.length()) {
            longestPalindrome = evenPalindrome;
        }
    }
    return longestPalindrome;
}

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

Output:

Longest Palindromic Substring: anana

Explanation:

The function longestPalindromicSubstring checks each character in the string as a potential center of a palindrome. It expands around this center to find the longest palindrome at that center, considering both odd and even lengths. 

For example, in the string "bananas", the longest palindromic substring is "anana". Similarly, in "abracadabra", the output is "aca", and for "dcabc", it is "d". The function ensures that the first longest palindrome found is returned in case of multiple occurrences.