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]
```

## Leave a Reply