#5 Longest Palindromic Substring

frequently reported atTCS Microsoft Bloomberg Amazon ByteDance / TikTok Walmart

the problem

In plain words

Return the longest contiguous substring of s that reads the same forwards and backwards. If there are ties, any one is accepted.

in s = "babad"

out "bab"

"aba" is also valid.

in s = "cbbd"

out "bb"

1 ≤ s.length ≤ 1000
Digits and English letters

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternExpand around center Interval DP

s[i..j] is a palindrome when its ends match and its inside s[i+1..j−1] is a palindrome. Equivalently, every palindrome grows outward from a centre.

solutions

From brute force to optimal

For all (i, j), test palindrome with two pointers.

Skip substrings no longer than the best so far.
Keep the longest palindrome.

timeO(n³)

n² substrings × O(n) check.

spaceO(1)

Indices only (plus the answer).

java

1class Solution {2    public String longestPalindrome(String s) {3        String best = "";4        for (int i = 0; i < s.length(); i++) {5            for (int j = i; j < s.length(); j++) {6                if (j - i + 1 > best.length() && isPalindrome(s, i, j)) best = s.substring(i, j + 1);7            }8        }9        return best;10    }11 12    private boolean isPalindrome(String s, int lo, int hi) {13        while (lo < hi) if (s.charAt(lo++) != s.charAt(hi--)) return false;14        return true;15    }16}

pal[i][j] = ends match && pal[i+1][j−1], filled by increasing length.

Lengths 1 and 2 only need the ends to match.
Track the longest true cell.

timeO(n²)

n² intervals × O(1).

spaceO(n²)

The boolean table (1 MB for n = 1000).

java

1class Solution {2    public String longestPalindrome(String s) {3        int n = s.length(), start = 0, bestLen = 1;4        boolean[][] pal = new boolean[n][n]; // pal[i][j]: is s[i..j] a palindrome?5        for (int len = 1; len <= n; len++) {          // short intervals first6            for (int i = 0; i + len - 1 < n; i++) {7                int j = i + len - 1;8                // ends match AND the inside is a palindrome (inside of length <= 1 always is)9                pal[i][j] = s.charAt(i) == s.charAt(j) && (len <= 2 || pal[i + 1][j - 1]);10                if (pal[i][j] && len > bestLen) {11                    bestLen = len;12                    start = i;13                }14            }15        }16        return s.substring(start, start + bestLen);17    }18}

2n − 1 centres (characters and gaps); grow each while ends match.

For each c: expand(c, c) for odd, expand(c, c+1) for even.
Update the best start/end.

timeO(n²)

2n − 1 centres × up to O(n) expansion.

spaceO(1)

No table.

java

1class Solution {2    public String longestPalindrome(String s) {3        int start = 0, end = 0; // best palindrome is s[start..end]4        for (int c = 0; c < s.length(); c++) {5            int odd = expand(s, c, c);      // centre on a character: "aba"6            int even = expand(s, c, c + 1); // centre between two: "abba"7            int len = Math.max(odd, even);8            if (len > end - start + 1) {9                start = c - (len - 1) / 2;10                end = c + len / 2;11            }12        }13        return s.substring(start, end + 1);14    }15 16    /** Grows outward while both ends match; returns the palindrome length found. */17    private int expand(String s, int lo, int hi) {18        while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {19            lo--;20            hi++;21        }22        return hi - lo - 1;23    }24}

sim

Grow from every centre

loading simulation…

java

1class Solution {2    public String longestPalindrome(String s) {3        int start = 0, end = 0; // best palindrome is s[start..end]4        for (int c = 0; c < s.length(); c++) {5            int odd = expand(s, c, c);      // centre on a character: "aba"6            int even = expand(s, c, c + 1); // centre between two: "abba"7            int len = Math.max(odd, even);8            if (len > end - start + 1) {9                start = c - (len - 1) / 2;10                end = c + len / 2;11            }12        }13        return s.substring(start, end + 1);14    }15 16    /** Grows outward while both ends match; returns the palindrome length found. */17    private int expand(String s, int lo, int hi) {18        while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {19            lo--;20            hi++;21        }22        return hi - lo - 1;23    }24}

in the room

How to say it in the interview

talk track

Present the DP to show the interval-DP idea, then say expand-around-centre has the same time but O(1) space.

traps

Forgetting even-length palindromes ("abba" has a centre between the two b's).
Filling the DP table by i ascending: pal[i+1][j−1] isn't ready yet. Fill by length.

what they ask next

Follow-ups

Linear time?

Manacher's algorithm reuses mirror information for O(n). Rarely expected in interviews.

Longest Palindromic Subsequence (LC 516)?

Interval DP: dp[i][j] = 2 + dp[i+1][j−1] on match, else max(dp[i+1][j], dp[i][j−1]). Or LCS(s, reverse(s)).

before you submit

Edge cases to test

One character → itself.
No repeats ("ac") → any single character.
Even length: "cbbd" → "bb" needs the gap centre between the two b's.

practise next