Longest Palindromic Substring

Medium· expand around centre· palindrome

Problem

Return the longest contiguous substring that reads the same forwards and backwards. If several have the same maximum length, any one of them is acceptable.

Examples

Input: s = "forgeeksskeegfor"

Output: "geeksskeeg"

This even-length palindrome is centred between the two s characters.

Input: s = "abcba"

Output: "abcba"

Constraints

• 1 <= s.length <= 1000
• Digits and English letters only

Hints & approach

Hint 1

Every palindrome has a centre: either one character or the gap between two.

Hint 2

From each centre, expand outward while the characters on both sides match.

Hint 3

There are 2n - 1 centres, and each expansion is at most O(n).

Approachtry the hints first

Try every centre: each index (odd-length palindromes) and each gap between adjacent indices (even-length palindromes). From a centre, move two pointers outward while they stay in bounds and point at equal characters. Record the widest span found across all centres. This is O(n^2) time with O(1) space; Manacher's algorithm achieves O(n) but is rarely expected in interviews.

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

← PreviousString to Integer (atoi)Next →Zigzag Conversion