Given a string s, the objective is to locate and return longest substring that reads the same forwards and backwards.

Examples

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: s = "cbbd"
Output: "bb"

Input: s = "a"
Output: "a"

Input: s = "ac"
Output: "a"

1. Brute Force Enumeration

The most straightforward method involves generating every possible substring and verifying if it is a palindrome. To check a substring, we can use two pointers starting from the edges and moving inward. If characters mismatch, it is not a palindrome.

public String findLongestPalindrome(String input) {
    if (input == null || input.isEmpty()) {
        return "";
    }
    
    String longest = input.substring(0, 1);
    
    for (int i = 0; i < input.length(); i++) {
        for (int j = i; j < input.length(); j++) {
            if (isPalindrome(input, i, j)) {
                int currentLen = j - i + 1;
                if (currentLen > longest.length()) {
                    longest = input.substring(i, j + 1);
                }
            }
        }
    }
    return longest;
}

private boolean isPalindrome(String str, int left, int right) {
    while (left < right) {
        if (str.charAt(left) != str.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

This appproach is generally too slow for large inputs due to its high time complexity.

2. Center Expantion Technique

A palindrome expands symmetrically from a center. Instead of checking substrings after extracting them, we can iterate through the string and treat every character (and the gap between characters) as a potential center. We expand outwards as long as the characters match.

class Solution {
    private int maxLength = 0;
    private int centerIndex = 0;

    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        
        for (int i = 0; i < s.length(); i++) {
            // Expand from a single character center (odd length)
            expandFromCenter(s, i, i);
            // Expand from a gap center (even length)
            expandFromCenter(s, i, i + 1);
        }
        
        return s.substring(centerIndex, centerIndex + maxLength);
    }

    private void expandFromCenter(String str, int leftPtr, int rightPtr) {
        while (leftPtr >= 0 && rightPtr < str.length() && str.charAt(leftPtr) == str.charAt(rightPtr)) {
            leftPtr--;
            rightPtr++;
        }
        
        int len = rightPtr - leftPtr - 1;
        if (len > maxLength) {
            maxLength = len;
            centerIndex = leftPtr + 1;
        }
    }
}

3. Dynamic Programming

A substring s[i...j] is a palindrome if s[i] equals s[j] and the substring s[i+1...j-1] is also a palindrome. We can use a 2D boolean array dp where dp[i][j] is true if the substring from index i to j is a palindrome.

We iterate by substring length. All single characters are palindromes (dp[i][i] = true). Then we check for lengths 2 and up.

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String result = "";
        
        // l is the length of the substring
        for (int l = 1; l <= n; l++) {
            for (int i = 0; i <= n - l; i++) {
                int j = i + l - 1;
                
                // Check if characters at borders match
                if (s.charAt(i) == s.charAt(j)) {
                    // If length is 1 or 2, it's a palindrome
                    // Otherwise, check the inner substring
                    if (l <= 2) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                
                if (dp[i][j]) {
                    if (l > result.length()) {
                        result = s.substring(i, j + 1);
                    }
                }
            }
        }
        return result;
    }
}