🌉5. Longest Palindromic Substring

Medium | Grind 75 | March 7th Tuesday, 2023

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

Constraints:

• 1 <= s.length <= 1000

• s consist of only digits and English letters.

Example 1

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

Example 2

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

SOLUTION

To solve this problem, we need to examine every possible substring of the input string and check if it is a palindrome. However, we can optimize this process by noting that a palindrome is symmetrical around its center. Therefore, we can start by picking each character in the string as the center of a potential palindrome and expand outwards on both sides until we reach the end of the string or find a mismatch. We then repeat this process, but this time we consider each pair of adjacent characters as the center of a potential palindrome, and again we expand outwards on both sides. By doing this for every character and pair of adjacent characters in the string, we consider every possible palindrome in the string.

We keep track of the longest palindromic substring we have encountered so far and update it every time we find a longer one. Once we have checked every possible palindrome, we return the longest one we have found as the result.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = ""

        for i in range(len(s)): 
            # CASE 1: odd length palindrome
            left, right = i, i 
            while left >= 0 and right < len(s) and s[left] == s[right]: 
                if (right-left+1) > len(longest): 
                    longest = s[left: right+1]
                
                # move to check the next charactrers
                left -= 1
                right += 1
            

            #CASE 2: even length palindrome
            left, right = i, i+1
            while left >= 0 and right < len(s) and s[left] == s[right]: 
                if (right-left+1) > len(longest): 
                    longest = s[left: right+1]
                
                # move to check the next charactrers
                left -= 1
                right += 1

        return longest

TIME AND SPACE COMPLEXITY

TIME: O(n^2) where n is the length of the string. We iterate over every character once which is n. For every character, we again iterate n (technically n/2 since we iterate left and right at once) characters twice(one for each case) to find a palindromic substring. Therefore, the runtime is n*(n+n) or 2n^2.

SPACE: O(n) where n is the length of the string s. The full string s is a substring of itself. Therefore, in the worst case, our variable longest will be n characters long.

**written with help from ChatGPT