vizlearn

Longest palindromic substring

Interview QuestionsBy Updated

Expand around every centre. A palindrome is symmetric about its middle, so try each possible middle and grow outwards while the characters match. There are 2n − 1 centres, not n, because an even-length palindrome is centred between two characters. O(n²) time, O(1) space.

Overview

Why 2n − 1 centres

An odd-length palindrome like aba is centred on a character. An even-length one like abba is centred on the gap between two. So there are n character centres and n − 1 gap centres.

Forgetting the even case is the classic bug here: the code passes on racecar and fails on abba, which is exactly the sort of half-correct that survives a quick test.

StringsCoding problemMedium

Step through it

What to watch

  • Each centre grows outwards until the characters stop matching.
  • Odd and even centres are tried separately — that is the 2n−1.
  • Nothing is allocated; only indices move.

Say this out loud

"Expand around centres. 2n-1 centres because even-length palindromes sit between characters. O(n²) time but O(1) space, which beats the DP table. There's an O(n) algorithm - Manacher's - but I'd only reach for it if you want it."

Longest palindromic substring

Find the longest palindromic substring.

Why not dynamic programming

The DP formulation — dp[i][j] is true when s[i:j+1] is a palindrome — is also O(n²) time and additionally O(n²) space. Expanding around centres gets the same time in O(1) space and is shorter to write.

Mention the DP version, then say why you are not using it. Recognising that two solutions share a time bound and differ on space is the judgement being tested.

The O(n) answer, and when to mention it

Manacher's algorithm is O(n): it reuses the palindromes already found to skip work, in the same spirit as KMP's prefix table. It is long, fiddly, and almost never expected.

Name it, say it exists and that you would look it up rather than reconstruct it under time pressure. That reads as calibration; attempting it from memory and stalling does not.

Run it in Python

Expansion from both kinds of centre with each one's result printed, then the odd-only version failing on an even-length palindrome, and a brute-force check for agreement.

longest_palindrome.pyPython 3
Output
How the code works
  1. return lo + 1, hi - 1The loop exits one step past the last match, so both indices step back inside. Returning lo, hi directly is the off-by-one this function exists to contain.
  2. (centre, centre) and (centre, centre + 1)The two kinds of centre. Odd-length palindromes sit on a character, even-length ones between two — which is where 2n − 1 comes from.
  3. odd_centres_onlyKept to be wrong. It handles racecar correctly and misses abba entirely, which is the sort of failure that survives a careless test.
  4. b - a > end - startCompares spans rather than slicing to compare lengths. Slicing inside the loop would allocate on every centre for no reason.
Change one thing
  • Feed it a string of 2,000 identical characters. Every centre expands the whole way, which is the O(n²) worst case in full.
  • Return the span instead of the substring and slice once at the end — the same reasoning as the slicing question.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. How many centres does the expansion approach try?
  2. Compared with the DP table, expanding around centres is:
  3. The O(n) algorithm for this problem is:





 Cheat sheet
Longest palindromic substring
Expand around every centre. A palindrome is symmetric about its middle, so try each possible middle and grow outwards while the characters match. There are 2n − 1 centres, not n, because an even-length palindrome is centred between two characters. O(n²) time, O(1) space.
INTERVIEW · vizlearn.in/interview/longest-palindromic-substring.html
More in Interview
InterviewEdit distance (Levenshtein)InterviewMinimum window substringInterviewWhat is a Python list underneath?InterviewWhy does [[0]*3]*3 break?
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact