LeetCode #5: Longest Palindromic Substring

LeetCode Solutions

https://leetcode.com/problems/longest-palindromic-substring/

The solution to this problem involves the use of a two-pointer approach where we use the center of a potential palindrome to expand outwards to both the left and right to find the longest palindrome. We consider two cases, one where the center is a single character and another where it is a pair of characters.

Here are the steps to solve this problem:

  1. Define a helper function expand that takes in a string s, left and right indices left and right and returns the length of the longest palindrome substring that can be formed from expanding outwards from left and right.
  2. If the given string is empty or has length less than 1, return the string itself as the longest palindromic substring.
  3. Initialize variables start and end to 0, which will store the starting and ending indices of the longest palindromic substring found so far.
  4. For each character in the string, expand outwards from it using the expand function for two cases: one where the center is a single character and another where it is a pair of characters.
  5. Calculate the maximum length of the palindrome substring found and update start and end indices accordingly.
  6. Return the substring from start to end as the longest palindromic substring found.
  7. Done.

Here’s the code implementation of the above steps:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(s, left, right):
            l = left
            r = right
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l-=1
                r+=1
            return r - l - 1
        
        if not s or len(s) < 1: 
            return s
        
        start = end = 0
        for i in range(len(s)):
            len1 = expand(s, i, i)
            len2 = expand(s, i, i+1)
            max_len = max(len1, len2)
            if max_len > end - start:
                start = i - (max_len - 1) // 2
                end = i + max_len // 2
        
        return s[start:end+1]

Time and Space Complexity

The time complexity of this solution is O(n^2) as we need to iterate over all possible centers in the string and expand around them. The space complexity is O(1) as we are not using any additional data structure.