Find the longest palindromic substring

Q: Find the longest palindromic substring

This question evaluates string manipulation and algorithmic problem-solving skills, focusing on identifying palindromic substrings and reasoning about performance and edge cases. Commonly asked in the Coding & Algorithms domain to assess practical algorithmic application, it gauges understanding of time/space complexity, input constraints, and robustness in implementation.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem

Given a string s, find the longest contiguous substring of s that is a palindrome (reads the same forward and backward).

Input

A string s consisting of ASCII letters/digits (you may assume standard printable characters).

Output

Return one longest palindromic substring. If there are multiple valid answers with the same maximum length, return any of them.

Constraints

1 <= |s| <= 2000

Examples

Input: "babad" → Output: "bab" (or "aba" )
Input: "cbbd" → Output: "bb"

Notes

In the interview setting, you may be asked to explain the approach verbally (no code required), including time/space complexity and edge cases.