5. Longest Palindromic Substring

Intuition

A palindrome reads the same forward and backward. The idea is to treat each index (and gap between characters) in the string as a possible centre of a palindrome and expand outwards as long as the characters on both sides match.

This method ensures that we can detect both odd-length and even-length palindromes.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(N^2)$

Code

public String longestPalindrome(String inputString) {

    int maxLength = 0;           // Stores the length of the longest palindrome
    int startIndex = 0;          // Start index of the longest palindrome
    int endIndex = 0;            // End index of the longest palindrome

    for (int center = 0; center < inputString.length(); ++center) {

        // Odd-length palindrome: Expand with center at one character
        int left = center, right = center;
        while (left - 1 >= 0 && right + 1 < inputString.length() &&
               inputString.charAt(left - 1) == inputString.charAt(right + 1)) {
            left--;
            right++;
        }

        int currentLength = right - left + 1;
        if (currentLength > maxLength) {
            maxLength = currentLength;
            startIndex = left;
            endIndex = right;
        }

        // Even-length palindrome: Expand with center between two characters
        left = center;
        right = center + 1;
        if (right < inputString.length() && inputString.charAt(left) == inputString.charAt(right)) {
            while (left - 1 >= 0 && right + 1 < inputString.length() &&
                   inputString.charAt(left - 1) == inputString.charAt(right + 1)) {
                left--;
                right++;
            }

            currentLength = right - left + 1;
            if (currentLength > maxLength) {
                maxLength = currentLength;
                startIndex = left;
                endIndex = right;
            }
        }
    }

    // Return the longest palindromic substring
    return inputString.substring(startIndex, endIndex + 1);
}