Longest Palindromic Substring

Medium · 1-D Dynamic Programming

You are given a string made of letters and digits. Return the longest contiguous run of characters that reads the same forwards and backwards. If more than one substring of that maximum length exists, you only need to return one of them, but for grading purposes a single fixed expected answer is used for each test.

Examples

Input:  s = "babad"
Output: "bab"
Why:    "bab" and "aba" are both palindromes of length 3; "bab" is the one this problem's grader accepts here.

Input:  s = "cbbd"
Output: "bb"
Why:    "bb" is the longest palindromic run; no length-3 or longer palindrome exists in the string.

Input:  s = "a"
Output: "a"
Why:    A single character is trivially a palindrome and is the whole string.

Constraints

1 <= s.length <= 1000, s consists only of digits and English letters

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Longest Palindromic Substring

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Longest Palindromic Substring. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.