5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

Solution in python:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        maxlen, left, right = 1, 0, 1
        for i in range(len(s)):
            strlen = 1
            p = i - 1
            q = i + 1
            while p >= 0 and q < len(s) and s[p] == s[q]:
                strlen += 2
                if strlen > maxlen:
                    left = p
                    right = q + 1
                    maxlen = strlen
                p -= 1
                q += 1
        for i in range(len(s)):
            strlen = 0
            p = i
            q = i + 1
            while p>= 0 and q < len(s) and s[p] == s[q]:
                strlen += 2
                if strlen > maxlen:
                    left = p 
                    right = q + 1
                    maxlen = strlen
                p -= 1
                q += 1
        return s[left:right]

Complexity analysis:

• Time complexity: O(N^2)
• Space complexity: O(1)