DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Longest Palindromic Substring

mediumStrings

Problem statement

Given a string s, return its longest contiguous substring that reads the same forwards and backwards (a palindrome). A single character always counts as a palindrome, so the answer is never empty for a non-empty string.

If several substrings share the maximum length, returning any one of them is accepted. The solutions below return the one that starts furthest left.

Examples

Example 1

Input: s = "xabacabay"

Output: "abacaba"

Explanation: abacaba has length 7. No longer palindrome exists in the string.

Example 2

Input: s = "noonday"

Output: "noon"

Explanation: Palindromes can have an even length. Here the centre sits between the two o characters.

Hints

Approach

Expand around every centre instead of storing a table.

  1. For each index i, expand twice: once with both pointers at i (odd length) and once with pointers at i and i + 1 (even length).
  2. While both pointers are inside the string and point at equal characters, move them one step outwards.
  3. When expansion stops, the palindrome is s[l+1..r-1]. Keep the longest one seen.

There are 2n - 1 centres and each expansion is at most O(n), so the worst case is still O(n²), but it uses O(1) extra memory and in practice most expansions stop almost immediately. This is the version interviewers usually expect.

ComplexityTime O(n²)Space O(1)
Python
class Solution:
def longestPalindrome(self, s: str) -> str:
def expand(l: int, r: int) -> tuple[int, int]:
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return l + 1, r - l - 1 # start, length
start, best = 0, 0
for i in range(len(s)):
for l, r in ((i, i), (i, i + 1)):
st, length = expand(l, r)
if length > best:
start, best = st, length
return s[start:start + best]

Follow-up questions

  • Count how many palindromic substrings the string contains, instead of returning the longest.
  • Return the longest palindromic subsequence, where characters do not need to be contiguous.

Frequently asked questions

Yes, Manacher's algorithm finds the answer in O(n) by reusing mirror information around the rightmost palindrome found so far. It is rarely expected in an interview; knowing that it exists and explaining expand-around-centre well is usually enough.

An odd-length palindrome has a middle character, while an even-length one has a middle gap. Expanding only from (i, i) never finds noon.

Less often than parsing or interval problems. It appears in general coding rounds for platform and SRE roles, and the underlying skill, careful two-pointer index handling on strings, is the same one you use when tokenising log lines or config values.