Longest Palindromic Substring Problem and Solution

1. Introduction

The "Longest Palindromic Substring" problem involves finding the longest substring within a given string that is a palindrome. A palindrome is a string that reads the same forwards and backwards.

2. Solution in C++

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

string longestPalindrome(string s) {
    if (s.empty()) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substr(start, end - start + 1);
}

int expandAroundCenter(const string& s, int left, int right) {
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

// Example usage
int main() {
    string s = "babad";
    cout << "Longest Palindromic Substring: " << longestPalindrome(s) << endl;
    return 0;
}

Output:

Longest Palindromic Substring: bab

Explanation:

1. The function longestPalindrome iterates over each character in the string s.

2. For each character, it expands around the center (the character and the pair of characters) to find the longest palindrome.

3. expandAroundCenter checks for palindrome by expanding both ends.

4. If a longer palindrome is found, it updates the starting and ending positions.

5. Finally, the longest palindromic substring is returned using substr.

3. Solution in Java

public class LongestPalindromicSubstring {
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    // Example usage
    public static void main(String[] args) {
        String s = "babad";
        System.out.println("Longest Palindromic Substring: " + longestPalindrome(s));
    }
}

Output:

Longest Palindromic Substring: bab

Explanation:

1. The longestPalindrome method in Java works similarly to the C++ solution.

2. It iterates through the string s and uses expandAroundCenter to find the longest palindromic substring.

3. The method updates the start and end indices if a longer palindrome is found.

4. The longest palindrome is obtained using substring.

4. Solution in Python

def longest_palindrome(s):
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

    if not s:
        return ""

    start, end = 0, 0
    for i in range(len(s)):
        len1 = expand_around_center(i, i)
        len2 = expand_around_center(i, i + 1)
        max_len = max(len1, len2)
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2

    return s[start:end + 1]

# Example usage
s = "babad"
print("Longest Palindromic Substring:", longest_palindrome(s))

Output:

Longest Palindromic Substring: bab

Explanation:

1. The function longest_palindrome in Python also follows a similar approach.

2. It expands around each character and the space between characters to find palindromes.

3. The function expand_around_center checks for palindrome by expanding from the center.

4. It updates the start and end indices when a longer palindrome is found.

5. The longest palindromic substring is returned using slicing.