Longest Palindromic Substring

Problem Statement

Given a string s, return the longest palindromic substring in s. A substring is a contiguous part of the string. A palindrome reads the same forwards and backwards.

Example:

• Input: s = "babad"

• Output: "bab" (or "aba" — both are valid)

• Input: s = "cbbd"

• Output: "bb"

Noob-Friendly Explanation

Imagine you have a word and you want to find the longest piece of it (without skipping letters) that reads the same forwards and backwards. For "babad", the piece "bab" reads the same both ways. That's the longest such piece you can find.

Think of it like looking at a word in a mirror — you want the longest chunk that looks identical in the mirror.

Approach 1: Brute Force

Intuition

Check every possible substring of the string and see if it's a palindrome. Keep track of the longest one found.

Algorithm

1. Generate all substrings using two nested loops (start index i, end index j).
2. For each substring, check if it's a palindrome.
3. Track the longest palindrome found.

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String result = "";

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = s.substring(i, j + 1);
                if (isPalindrome(sub) && sub.length() > result.length()) {
                    result = sub;
                }
            }
        }
        return result;
    }

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

Complexity Analysis

• Time Complexity: O(n^3) - O(n^2) substrings and O(n) to check each one for palindrome.
• Space Complexity: O(1) - We only use a few variables (ignoring the output string).

Approach 2: Optimal (Expand Around Center)

Intuition

Every palindrome has a center. For odd-length palindromes, the center is a single character. For even-length palindromes, the center is between two characters. We can expand outward from every possible center and find the longest palindrome.

Algorithm

1. For each index i, try expanding around center for both odd-length (center = i) and even-length (center = i and i+1).
2. While expanding, if characters on both sides match, keep going.
3. Track the longest palindrome found.

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";

        int start = 0, maxLen = 0;

        for (int i = 0; i < s.length(); i++) {
            // Odd length palindrome (single character center)
            int len1 = expandAroundCenter(s, i, i);
            // Even length palindrome (two character center)
            int len2 = expandAroundCenter(s, i, i + 1);

            int len = Math.max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }

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

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - We have n centers and each expansion takes O(n) in the worst case.
• Space Complexity: O(1) - We only use a few variables.