Dynamic Programming · 080Medium
Longest Palindromic Substring
Given a string s, return the longest palindromic substring in it. If several are tied, any one of them is acceptable.
Constraints
- 1 <= s.length <= 1000
- s consists of digits and English letters.
Examples
longestPalindrome("babad") -> "bab" // "aba" is also valid
longestPalindrome("cbbd") -> "bb"
longestPalindrome("a") -> "a"
longestPalindrome("ac") -> "a" // any single char is acceptable
longestPalindrome("aaaa") -> "aaaa" // the whole string
longestPalindrome("forgeeksskeegfor") -> "geeksskeeg"Edge cases
- Single characters are palindromes.
- No palindrome longer than 1 means returning any single character.
Show the target complexity (spoiler)
- Naive
- O(n^3) time — check every substring for palindromicity.
- Target
- O(n^2) time, O(1) space — expand around each of the 2n - 1 possible centers. (Manacher's algorithm reaches O(n).)
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/09-dynamic-programming/080-longest-palindromic-substring.js ./practice c 080