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

Python-related posts Visit HERE

C++ related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE

Share the Knowledge