Longest Palindromic Substring in Java

This document provides a Java program to find the longest palindromic substring in a given string. The program uses a dynamic programming approach to efficiently solve the problem.

Java Program

/**
 * This class contains a method to find the longest palindromic substring in a given string.
 */
public class LongestPalindromicSubstring {

    /**
     * Finds the longest palindromic substring in the given string.
     * 
     * @param s The input string.
     * @return The longest palindromic substring.
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String longestPalindrome = "";

        // All substrings of length 1 are palindromes
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            longestPalindrome = s.substring(i, i + 1);
        }

        // Check for palindromes of length 2
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                longestPalindrome = s.substring(i, i + 2);
            }
        }

        // Check for palindromes of length greater than 2
        for (int length = 3; length <= n; length++) {
            for (int i = 0; i < n - length + 1; i++) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    if (length > longestPalindrome.length()) {
                        longestPalindrome = s.substring(i, j + 1);
                    }
                }
            }
        }

        return longestPalindrome;
    }

    public static void main(String[] args) {
        String input = "babad";
        String result = longestPalindrome(input);
        System.out.println("Longest palindromic substring of \"" + input + "\" is \"" + result + "\"");
    }
}
    

Explanation

This program defines a class LongestPalindromicSubstring with a static method longestPalindrome that finds the longest palindromic substring in a given string s.

1. Initialization: The program initializes a 2D boolean array dp where dp[i][j] indicates whether the substring from index i to j is a palindrome. It also initializes a variable longestPalindrome to store the longest palindrome found.
2. Single Character Palindromes: It marks all single-character substrings as palindromes and updates longestPalindrome if necessary.
3. Two-Character Palindromes: It checks all substrings of length 2 to see if they are palindromes.
4. Longer Palindromes: For substrings of length greater than 2, it checks if the substring s[i...j] is a palindrome by verifying the characters at the ends and checking the inner substring’s palindrome status.
5. Output: The main method tests the function with the input "babad" and prints the longest palindromic substring.

This approach ensures that we check all possible substrings and efficiently find the longest palindromic substring in O(n²) time.