Given a lowercase string s, print its longest substring that is a palindrome (reads the same forwards and backwards). If several have the same maximum length, print the one that starts first.
Constraints
- 1 ≤ |s| ≤ 3000
Input and output
- Input
- One line: s.
- Output
- The longest palindromic substring.
Examples
Input 1
forgeeksskeegforOutput
geeksskeeg"geeksskeeg" reads the same both ways and is the longest such piece.
Input 2
abcdOutput
aEvery single letter is a palindrome; the first one, "a", is printed.
Show hints
- Every palindrome has a centre: a letter (odd length) or a gap between two letters (even length).
- Expand outwards from each of the 2n − 1 centres.
Show the explanation
Expand around centres. For each index, grow a palindrome outwards while the letters on both sides match — once with the centre on a letter and once between two letters. Keep the longest found; update only on a strictly longer one so the earliest start wins ties. That is O(n²) time and O(1) space, simple enough to write under interview pressure. (Manacher's algorithm does it in O(n), but is rarely expected.)
Original UniCircle question. Last reviewed 22 Oct 2026.