dynamic-programming · Problem 4 of 5
Longest Palindromic Substring
medium
Amazon
Google
Meta
Microsoft
Bloomberg
AmazonGoogleMetaMicrosoftBloombergGiven a string s, return the longest palindromic substring in s.
A palindrome is a string that reads the same forward and backward.
longestPalindrome("babad") -> "bab" // "aba" is also valid
longestPalindrome("cbbd") -> "bb"
longestPalindrome("a") -> "a"Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Running is free — Submit is what records it. Or press ⌘↩
Tests
5 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| longestPalindrome("babad") | odd length palindrome | "bab" | — |
| longestPalindrome("cbbd") | even length palindrome | "bb" | — |
| longestPalindrome("a") | single character | "a" | — |
| longestPalindrome("racecar") | entire string palindrome | "racecar" | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n²)
- target space
- O(1) extra space
Expanding around all 2n-1 centers takes O(n) per center, achieving O(n²) time with constant auxiliary space.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left