Longest Palindromic Substring

leetcode.com

Problem Statement

Given a string s, return the longest palindromic substring.

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

---

Brute Force Intuition

In an interview, you can explain it like this:

Generate every possible substring and check whether it is a palindrome. Keep track of the longest valid palindrome.

This approach is simple but repeatedly checks the same characters.

Complexity

• Time Complexity: O(N³)
• Space Complexity: O(1)

Brute Force Code

class Solution {

    public String longestPalindrome(String s) {

        String ans = "";

        for (int i = 0; i < s.length(); i++) {

            for (int j = i; j < s.length(); j++) {

                String sub = s.substring(i, j + 1);

                if (isPalindrome(sub) &&
                    sub.length() > ans.length()) {

                    ans = sub;
                }
            }
        }

        return ans;
    }

    private boolean isPalindrome(String s) {

        int i = 0;
        int j = s.length() - 1;

        while (i < j) {

            if (s.charAt(i) != s.charAt(j))
                return false;

            i++;
            j--;
        }

        return true;
    }
}

---

Moving Towards the Optimal Approach

Instead of checking every substring,

think differently.

Every palindrome has a:

Center

Example:

Odd Length

racecar

Center = e

Even Length

abba

Center = bb

Expand from every possible center.

---

Pattern Recognition

Whenever you see:

• Palindrome
• Longest Palindrome
• Substring

Think:

Expand Around Center

---

Key Observation

Every palindrome originates from a center.

For every index:

Expand in two ways.

Odd Length

left = i

right = i

Example

racecar

---

Even Length

left = i

right = i + 1

Example

abba

Expand while:

Characters Match

Keep updating the longest palindrome.

---

Optimal Approach

For every index:

Expand:

(i, i)

and

(i, i+1)

Take the longer palindrome.

---

Optimal Java Solution

class Solution {

    int start = 0;
    int maxLength = 0;

    public String longestPalindrome(String s) {

        for (int i = 0; i < s.length(); i++) {

            expand(s, i, i);

            expand(s, i, i + 1);
        }

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

    private void expand(String s,
                        int left,
                        int right) {

        while (left >= 0 &&
               right < s.length() &&
               s.charAt(left) == s.charAt(right)) {

            left--;
            right++;
        }

        int len = right - left - 1;

        if (len > maxLength) {

            maxLength = len;

            start = left + 1;
        }
    }
}

---

Dry Run

Input

babad

---

Center = b

Expand:

b

Length:

1

---

Center = a

Expand:

bab

Length:

3

Answer:

bab

---

Center = b

Expand:

aba

Length:

3

Same length.

---

Final Answer:

bab

(or "aba" is also correct.)

---

Why Expand Around Center Works?

Every palindrome has exactly one center.

There are:

N

Odd Centers

+

N-1

Even Centers

Expand from each center only once.

This avoids generating all substrings.

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N²)
Space Complexity	O(1)

---

Interview One-Liner

Treat every index as the center of a palindrome and expand outward while the characters match to find the longest palindromic substring.

---

Pattern Learned

Palindrome

↓

Choose Center

↓

Expand Both Sides

Similar Problems

• Longest Palindromic Substring
• Palindromic Substrings
• Valid Palindrome
• Longest Palindrome
• Shortest Palindrome

---

Memory Trick

Think:

Every Palindrome

↓

Has A Center

↓

Expand

↓

Update Longest

Mental Model

For Every Index

↓

Odd Expansion

+

Even Expansion

↓

Longest Answer

Whenever you hear:

"Longest Palindromic Substring"

your brain should immediately think:

Expand Around Center