Problem 3.5 · StringsMedium

Longest Palindromic Substring

What it teaches: Every palindrome grows from a centre: try all 2n − 1 centres and expand, instead of checking all O(n²) substrings.

Practise it on judges as “Longest Palindromic Substring”.

The problem

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

Example 1

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

Example 2

Input: s = "racecar"
Output: "racecar"

Example 3

Input: s = "forgeeksskeegfor"
Output: "geeksskeeg"

Constraints

1 ≤ s.length ≤ 1000
Digits and English letters

Pattern clues in the wording

→ Palindrome + substring
→ n ≤ 1000 allows O(n²) but not O(n³)

These clues point to Expand Around Center: Treat every index (and every gap between two indexes) as the middle of a palindrome and grow outwards while both sides match.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public String longestPalindrome(String s) {
        return s.substring(0, 1);
    }

    private int expand(String s, int left, int right) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	s = "cbbd"	"bb"
2	s = "racecar"	"racecar"
3	s = "forgeeksskeegfor"	"geeksskeeg"

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Brute force: check every substring · O(n³)2. Optimal: expand around every centre · O(n²)

Brute force: check every substring

Time O(n³) Space O(1)

For every pair (i, j), check whether s[i..j] is a palindrome with two pointers, and keep the longest.

Approach 1

class Solution {
    public String longestPalindrome(String s) {
        int bestL = 0, bestR = 0;
        for (int i = 0; i < s.length(); i++)
            for (int j = i; j < s.length(); j++)
                if (j - i > bestR - bestL && isPal(s, i, j)) { bestL = i; bestR = j; }
        return s.substring(bestL, bestR + 1);
    }
    private boolean isPal(String s, int l, int r) {
        while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
        return true;
    }
}

Verdict: About 10⁹ / 6 steps at n = 1000: too slow in practice.

Optimal: expand around every centre

Time O(n²) Space O(1)

For each index i, expand from (i, i) for odd lengths and from (i, i + 1) for even lengths. expand returns the length of the palindrome found. Track the best start and length.

▶ Dry run: Trying centres in "cbbd"s = "cbbd"

↑L↑R

best(vars)

"c" (1)

Step 1/4Centre 'c': length 1. Gap c|b: 'c' ≠ 'b', length 0.

Approach 2

class Solution {
    public String longestPalindrome(String s) {
        int start = 0, bestLen = 0;
        for (int i = 0; i < s.length(); i++) {
            int odd = expand(s, i, i);
            int even = expand(s, i, i + 1);
            int len = Math.max(odd, even);
            if (len > bestLen) {
                bestLen = len;
                start = i - (len - 1) / 2;
            }
        }
        return s.substring(start, start + bestLen);
    }

    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;
    }
}

Verdict: 2n − 1 centres, each expanding at most n/2 steps. The expected interview answer.

Before you submit

Edge cases and common mistakes

Test these inputs

Single character
All characters the same
Two characters, equal or different
Even-length answer

Mistakes people make

Forgetting even-length centres.
Wrong start index: for a palindrome of length len centred at i, start = i − (len − 1) / 2.

Interview

Follow-up questions

Can it be done in O(n)?

How would you count all palindromic substrings instead?

Command Palette