5. Longest Palindromic Substring

Problem Statement in English

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

Approach

The naive approach would be to check all substrings of s and check if they are palindromes. This would take $O(n^3)$ time.

But we can do better. We can use dynamic programming to solve this problem in $O(n^2)$ time.

There’s 2 cases to consider when checking if a substring is a palindrome:

• the palindrome is of even length
• the palindrome is of odd length

We approach the problem by iterating through the string and checking if the substring centered at the current index is a palindrome.

We do this by checking if the characters at the left and right pointers are equal. If they are, we expand the pointers and check if the substring is a palindrome.

This gives us odd length palindromes. Since we start at one index and expand to its left and right.

We can also check for even length palindromes by starting at the current index and the next index. This gives us even length palindromes.

Take a look at the code now.

Solution in Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        length = len(s)

        def helper(l, r):
            res = ""
            while l >= 0 and r < length and s[l] == s[r]:
                res = max(res, s[l:r+1], key=len)
                l-=1
                r+=1

            return res

        for i in range(length):
            odd = helper(i,i)
            even = helper(i,i+1)

            res = max(res, odd, even, key=len)

        return res

Complexity

• Time: $O(n^2)$
  

• Space: $O(1)$
  Since we only a few variables to store the result and the length of the string.

And we are done.