Skip to content

5. Longest Palindromic Substring

Two Pointers String Dynamic Programming

Problem - Longest Palindromic Substring

Medium

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.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[True] * n for _ in range(n)]
        k, max_num = 0, 1

        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = False
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1]
                    if dp[i][j] and max_num < j - i + 1:
                        k, max_num = i, j - i + 1

        return s[k : k + max_num]

Submission Stats:

  • Runtime: 254 ms (84.02%)
  • Memory: 17.7 MB (96.15%)