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"))
    print(solution.longestPalindrome("babad")) # bab
    print(solution.longestPalindrome("a")) # a
    print(solution.longestPalindrome("cbbd")) # bb
    print(solution.longestPalindrome("abb")) # bb

if __name__ == "__main__": main()