# Longest palindromic substring challenge

**Problem statement**

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

**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 we will assume that `s[i]`

is the middle of palindromic substring. Obviously `s[i]`

is a palindrome of length . 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 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 and ) 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")) print(solution.longestPalindrome("babad")) # bab print(solution.longestPalindrome("a")) # a print(solution.longestPalindrome("cbbd")) # bb print(solution.longestPalindrome("abb")) # bb if __name__ == "__main__": main()