Longest Palindrome in a String

In this class, We discuss the Longest Palindrome in a String.

The reader can take the complete competitive coding course. Click Here.

Question:

Given a string S.

Find the longest palindromic substring in the string S.

If multiple substrings are of the same length, display the substring starting with the least index.

Time complexity: O(|S|^2)

Space complexity: O(1)

Example:

Input: aaaabbaa

Output: aabbaa

Example 2:

Input: abc

Output: a

If no palindrome exists in the string, display the first character.

Logic:

We explained the logic in the above video.

Code:

class Solution:

    def longestPalin(self, S):

        # code here

        s = S

        n = len(s)

        def LP(l,r):

            while r<n and l>=0:

                if s[l]!=s[r]:break

                l-=1

                r+=1

            return l+1 , r

        start, end =0,0

        for i in range(n):

            #odd case

            l, r = LP(i,i)

            if (r-l)>(end-start):

                end = r

                start = l

            #even case   

            l, r = LP(i,i+1)

            if (r-l)>(end-start):

                end = r

                start = l

        return s[start:end]

s=input()

ob=Solution()

k=ob.longestPalin(s)

print(k)