Longest Palindromic Substring problem and solution in Java and Python

This one’s a classic dynamic programming and two-pointer problem that’s very popular in FAANG interviews. Let’s go through it step by step 👇

---

🧩 Problem: Longest Palindromic Substring

Question: Given a string s, return the longest substring that is a palindrome.

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

---

💡 Examples

Input: s = "babad"
Output: "bab" or "aba"

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

---

🧠 Intuition

We need to find the longest substring that reads the same backward and forward.

For example:

b a b a d
|-----|

The substring "bab" and "aba" are both palindromes.

---

💬 Brute Force (O(n³))

Check every substring and test if it’s a palindrome — but that’s too slow for interviews.

So we use expand-around-center or dynamic programming.

---

⚙️ Optimized Approach — Expand Around Center (O(n²) Time, O(1) Space)

🧩 Idea:

A palindrome mirrors around its center.

We can have:

• Odd-length palindrome → e.g., "aba" (center at ‘b’)
• Even-length palindrome → e.g., "abba" (center between the two ‘b’s)

For each index i, we:

1. Expand around i (odd length)
2. Expand around i and i+1 (even length)
3. Keep track of the longest one found

---

✅ Java Solution

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 = expand(s, i, i);     // Odd length
            int len2 = expand(s, i, i + 1); // Even length
            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 expand(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
    }
}

---

✅ Python Solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s
        
        start, end = 0, 0
        
        def expand(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left - 1
        
        for i in range(len(s)):
            len1 = expand(i, i)      # Odd-length palindrome
            len2 = expand(i, i + 1)  # Even-length palindrome
            length = max(len1, len2)
            
            if length > end - start:
                start = i - (length - 1) // 2
                end = i + length // 2
                
        return s[start:end + 1]

---

🧩 Example Walkthrough

For s = "babad":

1. Center at index 0 → "b" (len = 1)
2. Center at index 1 → expand "aba" (len = 3)
3. Center at index 2 → expand "bab" (len = 3)
4. Center at index 3 → "ada" (len = 3) Result: "bab" or "aba"

---

⚖️ Complexity

Operation	Time	Space
Expand around center	O(n²)	O(1)

---

🧠 Dynamic Programming Approach (O(n²) Time, O(n²) Space)

You can also use a 2D DP table where:

• dp[i][j] = true if substring s[i...j] is a palindrome
• s[i] == s[j] and dp[i+1][j-1] is true

But this uses extra space, so expand-around-center is preferred in interviews.

---

🌍 Real-World Analogy

Imagine holding a mirror 🔍 in the middle of a word. If the left and right sides look exactly the same, it’s a palindrome! You just slide the mirror across all positions and find where the reflection is longest.

---