How do you find the longest palindromic substring?

Q: How do you find the longest palindromic substring?

**Target Audience:** Beginners preparing for coding interviews — no prior algorithms knowledge assumed **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First Imagine a long strip of paper with letters printed on it, and a small mirror you can stand upright on the strip. Wherever you put the mirror, you can check how far the letters on the left match their reflection on the right: "b a | a b" matches two letters on each side, "r a c e | c a r" fails at once. Every palindrome hidden in the strip has a **middle** where the mirror would stand, either **on** a letter ("ra**c**ecar") or **between** two letters ("ab|ba"). So instead of checking every one of th

The problem

Question presented to candidate: "Given a string, return the longest substring that is a palindrome. For example, babad gives bab or aba, and cbbd gives bb. Please write it in Python, and tell me the time and space cost."

What a strong answer should cover:

Every palindrome has a centre: n character centres and n - 1 gap centres; expand two pointers outward from each while the characters match.
Track the best (start, length) and slice once at the end; O(n^2) time, O(1) extra space.
The O(n^3) brute force and the O(n^2)-space DP as alternatives; Manacher as the O(n) follow-up.
Edge cases: empty string, single character, even-length palindromes, ties.
Python specifics: slicing (s[a:b]) copies, so do not slice inside the loop; [[False] * n] * n aliases one row n times; Python loops are slow enough that the O(n^3) brute force is unusable beyond a few hundred characters.

Clarifying questions expected:

"Substring or subsequence?"
"If there is a tie, which palindrome should I return?"

Code / implementation expected: Yes — longest_palindrome(s) in Python using expand-around-centre with index pointers.

strings
dp
expand-center

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — no prior algorithms knowledge assumed Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

Imagine a long strip of paper with letters printed on it, and a small mirror you can stand upright on the strip. Wherever you put the mirror, you can check how far the letters on the left match their reflection on the right: "b a | a b" matches two letters on each side, "r a c e | c a r" fails at once. Every palindrome hidden in the strip has a middle where the mirror would stand, either on a

The solution is hidden so you can try first

9 min read · 10 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonExpand around centre on normal and edge-case strings

Practice

PythonBrute force, DP, expand and Manacher agree, with work counters

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.