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.
Worked examples
Input: s = "forgeeksskeegfor"
Output: "geeksskeeg"
This even-length palindrome is centred between the two s characters.
Input: s = "abcba"
Output: "abcba"
Hints
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).
Solution approach
- 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.
- Dry-run the example, then check boundary cases before explaining time and space costs.
Complexity
O(n^2) time; O(1) auxiliary space.
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗