## fizzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Longest palindromic substring challenge

Sharing is caring!

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

Sample input 1

```babad
```

Output 1

```bab
```

Sample input 1

```cbbd
```

Output 1

```bb
```

Solution
We are going to iterate over each character in the input string and assume that each character we iterate over is the middle of a new potential palindromic substring.

For instance, if are currently at index $i$ we will assume that `s[i]` is the middle of palindromic substring. Obviously `s[i]` is a palindrome of length $1$. We will then try to extend this palindrome to the left and to the right as long as the left and right edges have the same character.
If we `s[left]` and `s[right]` are not equal anymore we have a palindrome `s[left + 1 ... r - 1]`:

```def extend(self, s, l, r):
while (l >= 0 and r < len(s) and s[l] == s[r]):
l -= 1
r += 1

return s[l+1:r]
```

Since $s$ can have even or odd number of characters we have to consider both cases when starting to extend our initial palindrome:

```res = self.extend(s, i, i) # odd
res = self.extend(s, i, i+1) # even
```

since in case of even our middle will consist of two characters (at indices $i$ and $i+1$) and not just one.

Full code

```class Solution(object):
def extend(self, s, l, r):
while (l >= 0 and r < len(s) and s[l] == s[r]):
l -= 1
r += 1

return s[l+1:r]

def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
ans = ''
for i in range(0, len(s)):
res = self.extend(s, i, i)
if len(res) > len(ans):
ans = res

res = self.extend(s, i, i+1)
if len(res) > len(ans):
ans = res

return ans

def main():
solution = Solution()
print(solution.longestPalindrome("zudfweormatjycujjirzjpyrmaxurectxrtqedmmgergwdvjmjtstdhcihacqnothgttgqfywcpgnuvwglvfiuxteopoyizgehkwuvvkqxbnufkcbodlhdmbqyghkojrgokpwdhtdrwmvdegwycecrgjvuexlguayzcammupgeskrvpthrmwqaqsdcgycdupykppiyhwzwcplivjnnvwhqkkxildtyjltklcokcrgqnnwzzeuqioyahqpuskkpbxhvzvqyhlegmoviogzwuiqahiouhnecjwysmtarjjdjqdrkljawzasriouuiqkcwwqsxifbndjmyprdozhwaoibpqrthpcjphgsfbeqrqqoqiqqdicvybzxhklehzzapbvcyleljawowluqgxxwlrymzojshlwkmzwpixgfjljkmwdtjeabgyrpbqyyykmoaqdambpkyyvukalbrzoyoufjqeftniddsfqnilxlplselqatdgjziphvrbokofvuerpsvqmzakbyzxtxvyanvjpfyvyiivqusfrsufjanmfibgrkwtiuoykiavpbqeyfsuteuxxjiyxvlvgmehycdvxdorpepmsinvmyzeqeiikajopqedyopirmhymozernxzaueljjrhcsofwyddkpnvcvzixdjknikyhzmstvbducjcoyoeoaqruuewclzqqqxzpgykrkygxnmlsrjudoaejxkipkgmcoqtxhelvsizgdwdyjwuumazxfstoaxeqqxoqezakdqjwpkrbldpcbbxexquqrznavcrprnydufsidakvrpuzgfisdxreldbqfizngtrilnbqboxwmwienlkmmiuifrvytukcqcpeqdwwucymgvyrektsnfijdcdoawbcwkkjkqwzffnuqituihjaklvthulmcjrhqcyzvekzqlxgddjoir"))