103.Longest Palindromic Substring

MediumBlind 751-D Dynamic Programming · 5/12

Problem

Given a string s, return the longest contiguous substring of s that reads the same forwards and backwards.

If several palindromes share the maximum length, any one of them is accepted.

Examples

Input:  s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer — both have length 3.

Input:  s = "cbbd"
Output: "bb"
Explanation: An even-length palindrome centred between the two b's.

Input:  s = "a"
Output: "a"

Constraints

1 <= s.length <= 1000
s consists of only digits and English letters.

💡 Key Insight

A substring s[i..j] is a palindrome iff its ends match and its inside s[i+1..j-1] is a palindrome: pal(i, j) = s[i] == s[j] && pal(i + 1, j - 1), with every length-0 or length-1 string a palindrome. That recurrence gives an O(n²) DP. Flipping it around, every palindrome grows outward from a centre (a character or the gap between two), so expanding from all 2n - 1 centres finds the answer in O(n²) time with O(1) space. Manacher's algorithm reuses the mirror image of already-found palindromes to make the expansions linear overall — O(n).

Brute Force

TimeO(n³)SpaceO(1)

Intuition

Check every substring with a two-pointer palindrome test and keep the longest one that passes.

Algorithm

For every i and every j >= i:
Test s[i..j] by moving pointers inward from both ends.
If it is a palindrome and j - i + 1 beats the best length, record start = i, bestLen = j - i + 1.
Return s.substring(start, start + bestLen).

Visualization

s = "cbbd"
len 1: c b b d          all palindromes → best = "c"
len 2: cb ✗  bb ✓  bd ✗  → best = "bb"
len 3: cbb ✗ bbd ✗
len 4: cbbd ✗
answer "bb"

Code

java

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int start = 0, bestLen = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i + bestLen; j < n; j++) { // only lengths that could beat the best
                if (isPalindrome(s, i, j)) {
                    start = i;
                    bestLen = j - i + 1;
                }
            }
        }
        return s.substring(start, start + bestLen);
    }

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

Complexity

Time: O(n³) — O(n²) substrings, each checked in O(n).
Space: O(1) — only indices.

Top-Down Memoization

TimeO(n²)SpaceO(n²)

Intuition

The brute force re-verifies the same inner substrings over and over: checking s[0..4] checks s[1..3] and s[2..2], and later checking s[1..3] on its own does it again. Write the palindrome test recursively and cache pal(i, j) so each pair is answered once.

Recurrence: pal(i, j) = true if i >= j; otherwise pal(i, j) = (s[i] == s[j]) && pal(i + 1, j - 1).

Algorithm

memo[i][j] is a Boolean (null = unknown).
pal(i, j): base case i >= j → true; return the cached value if present; otherwise compute with the recurrence and cache it.
Loop over all pairs (i, j), and whenever pal(i, j) and the length beats the best, record it.

Visualization

s = "ababa". Different outer queries funnel into the same inner subproblems — those shared nodes are what the cache saves.

flowchart TD
    A["pal(0,4) 'ababa'"] --> B["pal(1,3) 'bab'"]
    B --> C["pal(2,2) 'a' = true"]
    D["pal(0,2) 'aba'"] --> E["pal(1,1) = true"]
    F["pal(2,4) 'aba'"] --> G["pal(3,3) = true"]
    H["query pal(1,3) again"] -->|"cache hit"| B
    I["pal(1,4) 'baba'"] -->|"b != a"| J["false, no recursion"]

Code

java

class Solution {
    private Boolean[][] memo;
    private String s;

    public String longestPalindrome(String s) {
        this.s = s;
        int n = s.length();
        memo = new Boolean[n][n];
        int start = 0, bestLen = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (j - i + 1 > bestLen && pal(i, j)) {
                    start = i;
                    bestLen = j - i + 1;
                }
            }
        }
        return s.substring(start, start + bestLen);
    }

    private boolean pal(int i, int j) {
        if (i >= j) {
            return true; // empty or single character
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        boolean result = s.charAt(i) == s.charAt(j) && pal(i + 1, j - 1);
        memo[i][j] = result;
        return result;
    }
}

Complexity

Time: O(n²) — each (i, j) pair is computed once with O(1) work.
Space: O(n²) — the memo table (recursion depth is at most n/2).

Bottom-Up Tabulation

TimeO(n²)SpaceO(n²)

Intuition

dp[i][j] depends on dp[i + 1][j - 1] — the cell one row below and one column left. So iterate i from n - 1 down to 0 and j from i up to n - 1; the needed cell is always filled already.

Recurrence: dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]).

Algorithm

boolean[][] dp = new boolean[n][n].
For i = n-1 .. 0, for j = i .. n-1: apply the recurrence.
If dp[i][j] and j - i + 1 > bestLen, record start = i, bestLen.
Return the recorded substring.

Dry Run

s = "cbbd" (T = palindrome, . = not, blank = j < i):

i \ j	0 c	1 b	2 b	3 d
0 c	T	.	.	.
1 b		T	T	.
2 b			T	.
3 d				T

dp[1][2]: s[1] == s[2] and length 2 → true. Longest true cell is (1, 2) → "bb".

Code

java

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0, bestLen = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                // ends match and the inside (if any) is a palindrome
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]);
                if (dp[i][j] && j - i + 1 > bestLen) {
                    start = i;
                    bestLen = j - i + 1;
                }
            }
        }
        return s.substring(start, start + bestLen);
    }
}

Complexity

Time: O(n²) — fill an n × n triangle.
Space: O(n²) — the table.

Expand Around Center

TimeO(n²)SpaceO(1)

Intuition

Every palindrome is symmetric around a centre. There are 2n - 1 centres: each character (odd length) and each gap between neighbours (even length). From each centre, push l left and r right while s[l] == s[r]. This visits exactly the same "is the inside a palindrome" chain as the DP, without storing it.

Algorithm

For each i: expand from (i, i) and from (i, i + 1).
expand(l, r): while in bounds and s[l] == s[r], l--, r++. The palindrome is s[l+1 .. r-1], length r - l - 1.
Keep the longest; return it.

Dry Run

flowchart LR
    A["s = 'babad'<br/>centre i=1 ('a')"] --> B["l=1, r=1<br/>a == a"]
    B --> C["l=0, r=2<br/>b == b"]
    C --> D["l=-1, r=3<br/>out of bounds, stop"]
    D --> E["palindrome s[0..2] = 'bab'<br/>length 3"]

Code

java

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);       // centre on a character
            int even = expand(s, i, i + 1);  // centre between two characters
            int len = Math.max(odd, even);
            if (len > bestLen) {
                bestLen = len;
                start = i - (len - 1) / 2;   // works for both odd and even lengths
            }
        }
        return s.substring(start, start + bestLen);
    }

    // returns the length of the longest palindrome centred at (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;
    }
}

Complexity

Time: O(n²) — 2n - 1 centres, each expanding up to O(n).
Space: O(1) — a few indices.

Manacher's AlgorithmOptimal

TimeO(n)SpaceO(n)

Intuition

Insert # between characters (plus sentinels ^ and $) so every palindrome becomes odd-length: "babad" → ^#b#a#b#a#d#$. Let p[i] be the radius of the longest palindrome centred at i in this transformed string t; then p[i] equals the palindrome's length in the original string.

Track the palindrome reaching furthest right, with centre center and right edge right. For a new i < right, its mirror 2*center - i lies inside that big palindrome, so p[i] is at least min(right - i, p[mirror]) — we start expanding from there instead of from zero. Since right only ever moves right, the total expansion work is O(n).

Algorithm

Build t = "^#" + s[0] + "#" + ... + "#$"; p = new int[t.length].
For i = 1 .. m-2:
- If i < right: p[i] = min(right - i, p[2*center - i]).
- While t[i + p[i] + 1] == t[i - p[i] - 1]: p[i]++ (sentinels stop it at the ends).
- If i + p[i] > right: center = i, right = i + p[i].
Take the i with maximal p[i]; the original start index is (i - p[i]) / 2.

Dry Run

s = "babad" → t = ^ # b # a # b # a # d # $:

i	0	1	2	3	4	5	6	7	8	9	10	11	12
t[i]	^	#	b	#	a	#	b	#	a	#	d	#	$
p[i]	0	0	1	0	3	0	3	0	1	0	1	0	0

Max p = 3 at i = 4 → start (4 - 3) / 2 = 0, length 3 → "bab". At i = 6, the mirror is 2*4 - 6 = 2 with p[2] = 1, so expansion starts at radius 1 instead of 0.

Code

java

class Solution {
    public String longestPalindrome(String s) {
        // transform "abc" -> "^#a#b#c#$" so every palindrome has odd length
        StringBuilder sb = new StringBuilder("^");
        for (char c : s.toCharArray()) {
            sb.append('#').append(c);
        }
        sb.append("#$");
        char[] t = sb.toString().toCharArray();
        int m = t.length;
        int[] p = new int[m];
        int center = 0, right = 0;

        for (int i = 1; i < m - 1; i++) {
            if (i < right) {
                // reuse the mirror's radius, capped by the known boundary
                p[i] = Math.min(right - i, p[2 * center - i]);
            }
            // expand; '^' and '$' differ from everything, so no bounds checks
            while (t[i + p[i] + 1] == t[i - p[i] - 1]) {
                p[i]++;
            }
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }

        int bestLen = 0, bestCenter = 0;
        for (int i = 1; i < m - 1; i++) {
            if (p[i] > bestLen) {
                bestLen = p[i];
                bestCenter = i;
            }
        }
        int start = (bestCenter - bestLen) / 2; // map back to an index in s
        return s.substring(start, start + bestLen);
    }
}

Complexity

Time: O(n) — right only increases, so the inner while runs O(n) times in total.
Space: O(n) — the transformed string and the p array.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n³)	O(1)
Top-Down Memoization	O(n²)	O(n²)
Bottom-Up Tabulation	O(n²)	O(n²)
Expand Around Center	O(n²)	O(1)
Manacher's Algorithm	O(n)	O(n)

Common Pitfalls

Only expanding odd-length centres — "cbbd" would return "c" instead of "bb".
Filling the DP table with i increasing: dp[i + 1][j - 1] would not be ready yet.
Off-by-one when converting an expansion back to a substring: after the loop the palindrome is s[l+1 .. r-1], not s[l .. r].
Confusing this with Longest Palindromic Subsequence — here the characters must be contiguous.
In an interview, Expand Around Center is the expected answer; mention Manacher as the O(n) follow-up.