Longest Palindromic Substring - Java Solution

1. Introduction

This blog post discusses the "Longest Palindromic Substring" problem, a classic problem in string processing. A palindrome is a string that reads the same forward and backward, and the task here is to find the longest palindromic substring within a given string. This problem is commonly encountered in areas like text processing and bioinformatics.

Problem

Given a string s, the objective is to find and return the longest palindromic substring in s. The solution should identify the substring that is a palindrome and has the maximum length among all possible palindromic substrings in s.

2. Solution Steps

1. Iterate through each character in the string, treating each character as the center of a potential palindrome.

2. For each center, expand around it to check for the longest palindrome. Consider both odd and even length palindromes.

3. Keep track of the start and end indices of the longest palindrome found.

4. Return the substring of s that corresponds to these indices.

3. Code Program

public class LongestPalindromicSubstring {
    private int start, maxLen;

    public static void main(String[] args) {
        LongestPalindromicSubstring solution = new LongestPalindromicSubstring();
        String s = "babad";
        System.out.println(solution.longestPalindrome(s)); // Test the function
    }

    // Function to find the longest palindromic substring
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) return s;

        for (int i = 0; i < len - 1; i++) {
            extendPalindrome(s, i, i); // Check for odd length palindrome
            extendPalindrome(s, i, i + 1); // Check for even length palindrome
        }
        return s.substring(start, start + maxLen);
    }

    // Helper function to extend a palindrome around a center
    private void extendPalindrome(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        if (maxLen < right - left - 1) {
            start = left + 1;
            maxLen = right - left - 1;
        }
    }
}

Output:

"bab" or "aba" (both are correct as the string contains two longest palindromes of the same length)

Explanation:

1. longestPalindrome: This function looks for the longest palindromic substring in the given string s. It handles strings with less than two characters by returning them as they are already palindromes.

2. The function iterates over each character, considering it as the center of a potential palindrome. It checks for both odd and even length palindromes using the extendPalindrome helper function.

3. extendPalindrome: This function expands around the center (left and right pointers) to find the longest palindrome at that center. It updates the start and maxLen variables if a longer palindrome is found.

4. The function returns the longest palindrome substring based on the updated start and maxLen.

5. This approach effectively identifies the longest palindromic substring by examining all possible centers and expanding around them to check for palindrome properties.