Longest palindromic substring

mediumDynamic programming, 2D target 25 min

Longest palindromic substring

Not solved yetLeetCode 5. Longest Palindromic Substring

A palindrome reads the same forwards and backwards, like "level" or "noon". A substring is a run of letters that sit next to each other in the string: unlike a subsequence, nothing in the middle may be skipped.

You get a string s. Find the longest stretch of s that is also a palindrome, and return that substring itself, not its length. When several share the greatest length, return the one that starts first. Every single letter is a palindrome, so an answer always exists.

Example 1

Inputs = "banana"Output"anana"

Positions 1 to 5. "ana" and "nan" are palindromes too, but shorter.

Example 2

Inputs = "noonday"Output"noon"

A palindrome of even length: its middle sits between the two o's.

Example 3

Inputs = "abacdc"Output"aba"

"aba" and "cdc" both have length 3, and "aba" starts first.

Example 4

Inputs = "pqr"Output"p"

No two letters are equal, so every palindrome is one letter long, and "p" starts first.

Constraints

1 ≤ len(s) ≤ 1,500
s uses only lowercase English letters.

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern