Longest Palindromic Substring

MediumString DP · Expand Around Centre🧩 String DP LeetCode #5 ↗Updated Oct 30, 2026

Problem

Given a string s, return its longest contiguous piece that reads the same forwards and backwards. If several pieces tie for the maximum length, any one of them is accepted.

Inputs = "babad"Output"bab" ("aba" is also fine)

Inputs = "cbbd"Output"bb"

Inputs = "x"Output"x"

1 ≤ s.length ≤ 1000 · s holds only digits and English letters

Try it yourself

Java

class Solution {
    public String longestPalindrome(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Every palindrome is a mirror around a centre — a single char (odd length) or a gap between two chars (even length). There are only 2n-1 centres, and growing outwards from each one finds every palindrome without any table.

PatternString DP

Instinct Two strings compared char by char (match, edit, interleave) means dp[i][j] over prefixes; one string's palindromes or splits means dp[l][r] or dp[i].

Memory hack Match? Go diagonal. Mismatch? Ask the neighbours. Up drops a char from s, left drops one from t, diagonal uses both.

Open the String DP guide →

Approaches

Brute ForceCheck Every Substring, Longest First

Time O(n³)Space O(1)

Try window lengths from n down to 1 and, for each start, test the window with two pointers. The first palindrome found is guaranteed to be a longest one.

Java

public String longestPalindrome(String s) {
    int n = s.length();
    for (int len = n; len >= 1; len--) {
        for (int i = 0; i + len <= n; i++) {
            if (isPalindrome(s, i, i + len - 1)) return s.substring(i, i + len);
        }
    }
    return "";
}

private boolean isPalindrome(String s, int l, int r) {
    while (l < r) {
        if (s.charAt(l++) != s.charAt(r--)) return false;
    }
    return true;
}

Obviously correct, but the inner palindrome check makes it cubic.

Better2-D Palindrome Table

Time O(n²)Space O(n²)

pal[i][j] is true when the ends match and the inside s[i+1..j-1] is a palindrome (or has length ≤ 1). Filling i from right to left guarantees the inner cell is ready, so each check is O(1).

Java

public String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] pal = new boolean[n][n];
    int start = 0, best = 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            // ends match and the middle (length <= 1, or pal[i+1][j-1]) is a palindrome
            if (s.charAt(i) == s.charAt(j) && (j - i < 3 || pal[i + 1][j - 1])) {
                pal[i][j] = true;
                if (j - i + 1 > best) {
                    best = j - i + 1;
                    start = i;
                }
            }
        }
    }
    return s.substring(start, start + best);
}

Quadratic time, but a million-cell boolean grid for n = 1000.

OptimalExpand Around Every Centre

Time O(n²)Space O(1)

For each index c expand twice: from (c, c) for odd lengths and from (c, c+1) for even ones, stopping at the first mismatch. The table's dependency chain is exactly this outward walk, so we can drop the table and keep only the best window.

Java

public String longestPalindrome(String s) {
    int start = 0, end = 0; // best window is s[start..end]
    for (int c = 0; c < s.length(); c++) {
        int len = Math.max(expand(s, c, c), expand(s, c, c + 1));
        if (len > end - start + 1) {
            start = c - (len - 1) / 2;
            end = c + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

// Length of the widest palindrome grown outward from (l, r).
private int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        l--;
        r++;
    }
    return r - l - 1;
}

Dry runs = "babad"

c centrel leftr right changed

c=0
b
c
a

b

a

d

"b", best=1
c=1
b
l
a
c
b
r
a

d

b==b → "bab", best=3
c=2
b

a
l
b
c
a
r
d

"aba" ties, keep
c=3
b

a

b
l
a
c
d
r
b≠d stop
c=4
b

a

b

a

d
c
answer "bab" ✔

Same time as the table, constant memory and short code — the expected answer.

Pro tip

Manacher's algorithm reuses mirror information to reach O(n); mention it, but centre expansion is what interviewers expect you to code.

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Substring, Longest First	`O(n³)`	`O(1)`
Better	2-D Palindrome Table	`O(n²)`	`O(n²)`
Optimal	Expand Around Every Centre	`O(n²)`	`O(1)`

Common pitfalls

Forgetting even-length centres — misses answers like "bb".
Wrong start index from a centre: use c - (len-1)/2, which works for odd and even.
Confusing substring with subsequence — that is a different (LPS 516) problem.

Interview tips

Clarify that any one of several tied answers is acceptable.
Explain why there are 2n-1 centres, then code the shared expand helper.
Note the table's O(n²) memory as the reason to prefer centre expansion.

Pattern

Expand around centre → any question about contiguous palindromes inside one string.

My notes saved in this browser