Back

5. Longest Palindromic Substring

Medium
Two Pointers
String
Dynamic Programming
Solve on LeetCode View Solutions

Description

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

 

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

Hints

Hint 1
How can we reuse a previously computed palindrome to compute a larger palindrome?
Hint 2
If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?
Hint 3
Complexity based hint:</br> 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.

Similar Questions

Shortest Palindrome
Hard
Palindrome Permutation
Easy
Palindrome Pairs
Hard
Longest Palindromic Subsequence
Medium
Palindromic Substrings
Medium
Maximum Number of Non-overlapping Palindrome Substrings
Hard

Statistics

Acceptance
37.0%
Submissions
11,956,598
Accepted
4,427,785