Longest Palindromic Substring Solution – Python LeetCode

LeetCode has a hard coding Problem in Its’ Algorithm Section: “Longest Palindromic Substring Solution From String”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE

Question

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"

Conditions

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Longest Palindromic Substring Solution

The Skeleton Code Given by LeetCode:

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

The goal is to create all palindromes of even and odd lengths while keeping track of the longest palindrome seen so far.

To make a palindrome with an odd length, For lengthier palindromes, fix a centre and expand in both directions, i.e. fix I (index) as the centre and two indices as i1 = i+1 and i2 = i-1. If i1 and i2 are equal, reduce i2 and raise i1 to get the maximum length.

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        longest = ""
        maxLength= 1
        start = 0
        low = 0
        high = 0
        string = s
        length = len(s)
        for i in range(1,length):

            low = i - 1
            high = i + 1
            while low >= 0 and high < length and string[low] ==string[high]:
                low -= 1
                high += 1

            low += 1
            high -= 1
            if string[low] == string[high] and high - low + 1 > maxLength:
              start = low
              maxLength = high - low + 1

Find the even-length palindrome using a similar method.
Take two indices, i1 = I and i2 = i-1, and compare characters at i1 and i2 to get the greatest length until all pairs of compared characters are identical.

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        longest = ""
        maxLength= 1
        start = 0
        low = 0
        high = 0
        string = s
        length = len(s)
        for i in range(1,length):
            low = i - 1
            high = i
            while low >= 0 and high < length and string[low] ==string[high]:
                low -= 1
                high += 1

            low += 1
            high -= 1
            if string[low] == string[high] and high - low + 1 > maxLength:
              start = low
              maxLength = high - low + 1

            low = i - 1
            high = i + 1
            while low >= 0 and high < length and string[low] ==string[high]:
                low -= 1
                high += 1
            low += 1
            high -= 1
            if string[low] == string[high] and high - low + 1 > maxLength:
              start = low
              maxLength = high - low + 1

        return string[start:start + maxLength]