Python 58 ms solution (beats 100%), using three pointers


  • 0
    J
    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            ls = len(s)
            maxs = ''
            i = 0
            # stop the iteration, if the (left characters * 2 - 1) is shorter than maxs
            while 2 * (ls - i) - 1 > len(maxs): 
                pl = pr = i
                # move the current index (i) and the right pointer (pr), if the consecutive letters are the same
                while pr < ls - 1 and s[pr] == s[pr + 1]:
                    i += 1
                    pr += 1
                
                # move left and right pointers, so that the substring between them is longer than maxs
                dif = len(maxs) - (pr - pl)
                if dif > 0: 
                    dif += dif%2
                    pl, pr = pl - dif/2, pr + dif/2
                    
                # check whether the substring is palindrome. 
                # If yes, try to further extend it, and then replace maxs with the new palindrome
                if s[pl:pr+1] == s[pr:(pl-1 if pl > 0 else None):-1]:
                    while pl > 0 and pr < ls -1 and s[pl-1] == s[pr+1]:
                        pl -= 1
                        pr += 1
                    maxs = s[pl:pr+1]
                print i, maxs
                i += 1
            return maxs
    s = 'abcddddcbaefg'
    Solution().longestPalindrome(s)  
    
    # outputs of index i and max substring (maxs) at each step
    0 a
    1 a
    2 a
    6 abcddddcba
    7 abcddddcba
    

    see how it jumps from 2 to 6 when "dddd" appear, and how it stop at i = 7, even though there are still several letters unexplored.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.