Longest Palindromic Substring - CPP Solution

1. Introduction

In this post, we will delve into a fascinating string processing problem: finding the longest palindromic substring in a given string. A palindrome is a string that reads the same backward as forward, and this problem is a common question in coding interviews, highlighting one's skills in dynamic programming and string manipulation in C++.

Problem

Given a string 's', the task is to return the longest palindromic substring in 's'. A palindromic substring is a substring which reads the same backward as forward.

Example 1:

Input: s = "babad"

Output: "bab" (Note: "aba" is also a valid answer.)

Example 2:

Input: s = "cbbd"

Output: "bb"

2. Solution Steps

1. Check for palindromic substrings by expanding around the center.

2. Consider each character and the gap between each character as potential centers.

3. Expand around each center and check for the longest palindrome.

4. Update the longest palindromic substring found so far.

5. Repeat this process for each center.

6. Return the longest palindromic substring.

3. Code Program

#include <iostream>
using namespace std;

// Helper function to expand around the center and find the longest palindrome
string expandAroundCenter(const string &s, int left, int right) {
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        left--;
        right++;
    }
    return s.substr(left + 1, right - left - 1);
}

// Function to find the longest palindromic substring
string longestPalindrome(string s) {
    if (s.empty()) return "";

    string longest = "";
    for (int i = 0; i < s.length(); i++) {
        // Expand around i as center for odd length palindrome
        string odd = expandAroundCenter(s, i, i);
        if (odd.length() > longest.length()) {
            longest = odd;
        }

        // Expand around i and i+1 for even length palindrome
        string even = expandAroundCenter(s, i, i + 1);
        if (even.length() > longest.length()) {
            longest = even;
        }
    }
    return longest;
}

int main() {
    string str = "babad";
    cout << "Longest palindromic substring: " << longestPalindrome(str) << endl;
    return 0;
}

Output:

Longest palindromic substring: bab

Explanation:

1. The input string "babad" is checked for palindromes by expanding around each character and the gap between characters.

2. For each character (like 'b', 'a', 'b'), an odd length palindrome is checked.

3. For each gap (like between 'b' and 'a', 'a' and 'b'), an even length palindrome is checked.

4. The longest palindrome found is "bab" (or "aba"), which is 3 characters long.

5. This approach ensures that all possible palindromic substrings are considered, resulting in the longest palindrome being correctly identified.