Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = “babad” Output: “bab” Explanation: “aba” is also a valid answer.

Example 2:

Input: s = “cbbd” Output: “bb”

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Approach: Expand Around Center (Optimal Solution)

Algorithm

1. Every palindrome is centered at either a single character (odd length) or between two characters (even length)
2. For each possible center, expand outward while the characters match
3. Track the longest palindrome found
4. There are 2n - 1 possible centers: n single characters and n - 1 gaps between characters

Key Insight

A palindrome mirrors around its center. Instead of checking every substring (O(n²) substrings with O(n) verification), we expand outward from each center, giving O(n²) total with a much simpler inner loop. Each expansion either finds the maximal palindrome at that center or stops at a mismatch.

Time & Space Complexity

• Time Complexity: O(n²) - two loops, each expansion is O(n) in the worst case
• Space Complexity: O(1) - only constant extra space used

Java Implementation

public class LongestPalindromicSubstring {

    /**
     * Find the longest palindromic substring in a string.
     * @param s Input string
     * @return Longest palindromic substring
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }

        int start = 0;
        int end = 0;

        for (int i = 0; i < s.length(); i++) {
            // Odd-length palindrome centered at i
            int len1 = expandAroundCenter(s, i, i);
            // Even-length palindrome centered between i and i+1
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);

            // Update the longest palindrome found
            if (len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1);
    }

    /**
     * Expand outward from a center while characters match.
     * @return Length of the palindrome found
     */
    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // right - left - 1 gives the palindrome length
        return right - left - 1;
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        System.out.println("Input: s = \"babad\"");
        System.out.println("Output: \"" + longestPalindrome("babad") + "\""); // Expected: "bab" or "aba"

        // Test case 2
        System.out.println("Input: s = \"cbbd\"");
        System.out.println("Output: \"" + longestPalindrome("cbbd") + "\""); // Expected: "bb"
    }
}

Example Walkthrough

For s = "babad":

1. i=0, center ‘b’: expand → “b” (len=1)
2. i=1, center ‘a’: expand → “aba” (len=3). Update longest: start=0, end=2
3. i=1, gap ‘a’-‘b’: no match (len=0)
4. i=2, center ‘b’: expand → “bab” (len=3). Update longest: start=1, end=3
5. i=2, gap ‘b’-‘a’: no match
6. i=3, center ‘a’: expand → “aba” (len=3)
7. i=4, center ‘d’: expand → “d” (len=1)

Longest palindrome = “bab” (or “aba”), length 3.

For s = "cbbd":

1. i=0, center ‘c’: expand → “c” (len=1)
2. i=1, center ‘b’: expand → “b” (len=1)
3. i=1, gap ‘b’-‘b’: expand → “bb” (len=2). Update longest: start=1, end=2
4. i=2, center ‘b’: expand → “bb” (len=2)
5. i=3, center ‘d’: expand → “d” (len=1)

Longest palindrome = “bb”, length 2.

Alternative Dynamic Programming Approach

public static String longestPalindromeDP(String s) {
    int n = s.length();
    if (n < 2) {
        return s;
    }

    boolean[][] dp = new boolean[n][n];
    int start = 0;
    int maxLen = 1;

    // Every single character is a palindrome
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    // Check substrings of length 2 and up
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j) && (len == 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (len > maxLen) {
                    maxLen = len;
                    start = i;
                }
            }
        }
    }

    return s.substring(start, start + maxLen);
}

The DP approach also runs in O(n²) time but uses O(n²) space, making the expand-around-center approach more space efficient.

Key Insights

1. Center-Based Expansion: A palindrome mirrors around its center, so expanding from 2n - 1 centers covers all palindromes
2. Odd and Even Cases: Handles both single-character and two-character centers
3. Constant Space: Unlike DP, no table is needed, keeping space at O(1)
4. Track Indices: Stores start and end indices rather than building substrings repeatedly

The expand-around-center approach is the optimal solution for this problem, providing O(n²) time complexity with constant space usage.