Longest Palindromic Substring - Java Solution

1. Introduction

In this blog post, we're going to explore a classic problem in string manipulation - finding the longest palindromic substring within a given string. This problem is a common question in coding interviews and is excellent for understanding string processing in Java.

Problem

Given a string s, the task is to find the longest palindromic substring in s.

Examples:

Input: "babad"

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

Input: "cbbd"

Output: "bb"

2. Solution Steps

1. If the input string is null or its length is less than 1, return an empty string.

2. Create two variables to store the start and end of the longest palindrome found.

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

4. Check for palindromes that have odd and even lengths and update the start and end variables if a longer palindrome is found.

5. After the iteration, return the substring from the start to the end + 1.

3. Code Program

public class Solution {
    // Main method to test the longest palindrome finder
    public static void main(String[] args) {
        String input1 = "babad";
        String input2 = "cbbd";
        System.out.println("Longest Palindromic Substring of '" + input1 + "': " + longestPalindrome(input1));
        System.out.println("Longest Palindromic Substring of '" + input2 + "': " + longestPalindrome(input2));
    }

    // Method to find the longest palindromic substring
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return ""; // Check for null or empty string
        int start = 0, end = 0; // Variables to mark the start and end of the longest palindrome

        for (int i = 0; i < s.length(); i++) {
            int len1 = expandFromCenter(s, i, i); // Length of palindrome for odd length
            int len2 = expandFromCenter(s, i, i + 1); // Length of palindrome for even length
            int len = Math.max(len1, len2); // Maximum length from the two cases

            if (len > end - start) { // Update start and end if a longer palindrome is found
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1); // Return the longest palindromic substring
    }

    // Helper method to expand around the center and find palindrome length
    private static int expandFromCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1; // Length of the palindrome
    }
}

Output:

Longest Palindromic Substring of 'babad': bab
Longest Palindromic Substring of 'cbbd': bb

Explanation:

For the input "babad", the longest palindromic substrings are "bab" and "aba", each with a length of 3. 

The method longestPalindrome checks for palindromes by expanding around potential centers of the palindrome (including handling both odd and even length palindromes). 

Similarly, for the input "cbbd", the longest palindromic substring is "bb". 

The algorithm efficiently finds the longest palindromic substring with a complexity of O(n^2), where n is the length of the string.