Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Input: "cbbd" Output: "bb"
- Shortest Palindrome (Hard)
- Palindrome Permutation (Easy)
- Palindrome Pairs (Hard)
- Longest Palindromic Subsequence (Medium)
- Palindromic Substrings (Medium)
Hint 1How can we reuse a previously computed palindrome to compute a larger palindrome?
Hint 2If “aba” is a palindrome, is “xabax” and palindrome? Similarly is “xabay” a palindrome?
Hint 3Complexity based hint:
If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.