1. Introduction

In this tutorial, we’ll explore how to find the longest palindromic substring within a given string in Java. A palindrome is a word, phrase, number, or other sequences of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization).

2. Program Steps

1. Create a Java class and define the main method.

2. Define the input string from which we want to find the longest palindromic substring.

3. Initialize variables to store the start index and maximum length of the longest palindromic substring.

4. Iterate through the string and for each character, expand around the center (considering both odd and even length palindromes) to find the longest palindromic substring.

5. Print the longest palindromic substring.

3. Code Program

public class LongestPalindromicSubstring {

    public static void main(String[] args) {
        // Step 2: Define the input string
        String str = "babad";

        // Step 3: Initialize variables
        int start = 0;
        int maxLength = 1;

        for (int i = 1; i < str.length(); i++) {
            // Step 4: For even length palindrome
            int low = i - 1;
            int high = i;
            while (low >= 0 && high < str.length() && str.charAt(low) == str.charAt(high)) {
                if (high - low + 1 > maxLength) {
                    start = low;
                    maxLength = high - low + 1;
                }
                --low;
                ++high;
            }

            // Step 4: For odd length palindrome
            low = i - 1;
            high = i + 1;
            while (low >= 0 && high < str.length() && str.charAt(low) == str.charAt(high)) {
                if (high - low + 1 > maxLength) {
                    start = low;
                    maxLength = high - low + 1;
                }
                --low;
                ++high;
            }
        }

        // Step 5: Print the longest palindromic substring
        System.out.println("Longest palindromic substring is: " + str.substring(start, start + maxLength));
    }
}

Output:

Longest palindromic substring is: bab

4. Step By Step Explanation

– Step 1: A Java class named LongestPalindromicSubstring is created, and the main method is defined.

– Step 2: The input string str is defined, for which we want to find the longest palindromic substring.

– Step 3: Variables start and maxLength are initialized to store the start index and maximum length of the longest palindromic substring.

– Step 4: We iterate through the string. For each character, we expand around the center for both odd and even length palindromes and update start and maxLength accordingly.

– Step 5: The longest palindromic substring is then printed using the substring method.

The program successfully finds and prints the longest palindromic substring in the given input string.