Problem Statement

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

A palindrome is a string that reads the same forward and backward.

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 consists of only digits and English letters.

---

Intuition

A palindrome has a symmetric property:

A substring is a palindrome if it reads the same when reversed.

For example:

• "aba" is a palindrome (same forward and backward).
• "abba" is also a palindrome.

We want the longest substring of s that satisfies this property.

---

Idea 1: Brute Force Approach (O(n³))

Steps:

1. Generate all possible substrings.
2. For each substring, check if it’s a palindrome.
3. Keep track of the longest one.

Although simple, this approach has O(n³) time complexity:

• Generating all substrings → O(n²)
• Checking each substring for palindrome → O(n)

This is too slow for long strings, so we need an optimized approach.

---

Idea 2: Expand Around Center (Optimized, O(n²))

Key Observation:
A palindrome can be centered at one or two characters:

1. Odd-length palindrome → single center (e.g., "aba")
2. Even-length palindrome → double center (e.g., "abba")

We expand around each possible center and check how far we can go while maintaining the palindrome property.

Steps:

1. Iterate over every index in the string as a potential center.
2. Expand outward (left and right) until characters are not equal.
3. Track the start and end indices of the longest palindrome found.

---

Java Solution (Expand Around Center)

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

        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            int len1 = expandFromCenter(s, i, i);       // Odd length palindrome
            int len2 = expandFromCenter(s, i, i + 1);   // Even length palindrome
            int len = Math.max(len1, len2);

            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

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

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

---

Complexity Analysis

• Time Complexity: O(n²)
  For each character, we expand in both directions (up to n characters).
• Space Complexity: O(1)
  No extra space used beyond a few variables.

---

Dry Run Example

Input: "babad"

We’ll analyze how the algorithm finds "bab".

Center	Expansion	Palindrome Found	Longest
i = 0 (‘b’)	Odd → "b", "bab"	"bab"	"bab"
i = 1 (‘a’)	Odd → "a", "aba"	"aba"	"bab" or "aba"
i = 2 (‘b’)	Odd → "b"	"b"	"bab"
i = 3 (‘a’)	Odd → "a"	"a"	"bab"
i = 4 (‘d’)	Odd → "d"	"d"	"bab"

Final longest palindrome = "bab" (or "aba").

---

Alternate Approach: Dynamic Programming (O(n²) Time, O(n²) Space)

Idea:
Use a 2D DP table where dp[i][j] = true if substring s[i...j] is a palindrome.

Transitions:

1. If s[i] == s[j] and:
   • Substring length ≤ 3, or
   • dp[i+1][j-1] is true
     Then dp[i][j] = true.
2. Update max length and start index accordingly.

Code (DP Version)

public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLen = 1;

        for (int i = 0; i < n; i++)
            dp[i][i] = true; // single char is palindrome

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;

                if (s.charAt(i) == s.charAt(j)) {
                    if (len == 2 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;

                        if (len > maxLen) {
                            start = i;
                            maxLen = len;
                        }
                    }
                }
            }
        }

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

---

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Comments
Brute Force	O(n³)	O(1)	Too slow
Dynamic Programming	O(n²)	O(n²)	Easier to understand
Expand Around Center	O(n²)	O(1)	Best in practice

---

Key Takeaways

1. Every palindrome is symmetric around a center.
2. Expanding around every possible center efficiently finds all palindromes.
3. Always update start and end when a longer palindrome is found.
4. Dynamic programming gives insight into the structure but uses more space.