5. Longest Palindromic Substring

MediumOne-Dimensional Dynamic ProgrammingTwo-pointer expansion over palindrome centersExpand around center

Longest Palindromic Substring

Given a string s, return the longest contiguous substring of s that reads the same forwards and backwards. If several have the maximum length, any one of them is accepted.

Open official problem prompt ↗

In plain English

Find the longest stretch of consecutive characters that is a mirror image of itself.

Picture it like this

Standing at each seam of a row of tiles and pushing both hands outward as long as the tiles on the left and right match -- the widest symmetric span you reach is the answer.

Example

Input: s = "babad"
Output: "bab"
Why: "bab" is a palindrome of length 3; "aba" is an equally valid alternative.

Constraints

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

Pattern lesson

See the pattern, then code

Expand around center

↗

One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. Every palindrome has a center; expanding two pointers outward while characters match finds the longest palindrome anchored at that center.

New words, made simpleKnow these before the algorithm

Palindrome: A string equal to its own reverse.
Center: A single character (odd length) or a gap between two characters (even length) around which a palindrome is symmetric.
Substring: A contiguous slice of the string.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Check every substring

The palindrome test adds another factor of n; too slow.

For all O(n^2) substrings test whether each is a palindrome.

Time O(n^3)Space O(1)

Best choiceExpand around center

Simple, constant extra space, fast enough for n<=1000.

Grow outward from each of the 2n-1 centers.

Time O(n^2)Space O(1)

The rule we keep true

Invariant

After processing center i, (start, end) records the longest palindrome found among all centers up to and including i.

Why this is correct

Reasoning

Every palindrome is uniquely determined by its center and expands symmetrically; there are exactly 2n-1 centers (n single characters and n-1 gaps). Checking maximal expansion at each center therefore examines every palindrome's longest form, so the global maximum is found.

The algorithm in three movesSay these aloud before coding

1Iterate every index as a potential center

center i=1 odd: expand 'a' -> 'bab'

2Expand once treating i as an odd-length center and once treating i,i+1 as an even-length center

best span (0,2)

3Each expansion widens while both ends match and stay in bounds

even centers yield nothing longer

4Track the widest span seen and return that slice

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readodd center 0

2 · Askexpand while equal?

3 · Update statespan (0,0)

4 · Resultleft goes out of bounds immediately; length 1.

Key takeaway

Expanding around index 1 grows outward to the palindrome 'bab'.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Guard and best span
Handle empty input and remember the best (start, end) window found so far.
2
Lines 6-10Expansion helper
Widen l and r while in bounds and matching, then return the last valid inclusive span (l+1, r-1).
3
Lines 11-17Try both center types
For every index run one odd expansion and one even expansion, updating the best window when a wider palindrome appears.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single character returns that character
All identical characters returns the whole string
No palindrome longer than 1 (e.g. 'abc') returns any single character
Even-length palindrome like 'cbbd' must be caught by the even center

Common beginner mistakes

Forgetting even-length centers and missing palindromes like 'abba'
Off-by-one when converting the expansion's final l,r back to the valid inclusive span (l+1, r-1)
Comparing lengths with r-l+1 inconsistently versus r-l when updating the best

Check your understanding

Why must you expand around both a single index and a pair of adjacent indices?

PyPython 3 · solution.py

Optimal

1class Solution:2    def longestPalindrome(self, s: str) -> str:3        if not s:4            return ""5        start, end = 0, 06        def expand(l: int, r: int) -> tuple[int, int]:7            while l >= 0 and r < len(s) and s[l] == s[r]:8                l -= 19                r += 110            return l + 1, r - 111        for i in range(len(s)):12            l1, r1 = expand(i, i)13            if r1 - l1 > end - start:14                start, end = l1, r115            l2, r2 = expand(i, i + 1)16            if r2 - l2 > end - start:17                start, end = l2, r218        return s[start:end + 1]

Time complexityO(n^2)Optimized

Space complexityO(1)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftAdobe

Longest Palindromic Substring

Longest Palindromic Substring

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in One-Dimensional Dynamic Programming