My thought of solving this problem with O(n * log(n)) complexity, please advise


  • 0
    D

    This problem can be interpreted as:

    1. A reduced problem: given string S and constant length L, return the
      palindrome (if exist).
      -Now I only get O(n^2) solution for this reduced problem, but I believe that there are O(n) solution to this sub problem, since there is already O(n) solution to the original problem O(n) solution

    2. A Bi-Search process to find the longest length for the reduced problem. Note that if there exists a palindrome of length N (N>=2), there must be palindrome of length N-2. This makes me think of
      Binary-Search method. For example, Given string S length of 10. Then the possible palindrome length falls in two search zones: odd = [1,3,5,7,9] even = [2,4,6,8,10] Then we perform bi-search in these two zone separately.


    Because the complexity of bi-search is O(log(n)), so the overall complexity = O(n*log(n))


  • 0
    D

    Below is my accepted solution of 888 ms:

    class Solution(object):
        def longestPalindrome(self,s):
            """
            :type s: str
            :rtype: str
            """
            def searchForPal(try_len, s):
                """
                Give string s, and a length, determin if s contains a palindromic substring of length try_len
                input: string s
                output: pal or None
                """
                L = len(s)
                #Shift window of length = try_len
                start = 0
                end = start + try_len - 1
                while 0 <= start <= end <= L-1:
                    #print "try_len, start, end ",try_len, start, end
                    #Test if the substring inside this window satisfy Pal condition
                    st = start
                    e = end
                    while start <= st <= e <= end:
                        if s[st] != s[e]:
                        #condition not met, move to next window
                            start += 1
                            end += 1 
                            break
                        else:
                            st += 1
                            e -=1
                    if st >= e: #The Pal check finished with no failure
                        return s[start: end+1]
                return ''
    
            # Pad # sign
            temp, s =s, '#'
            for c in temp:
                s += c + '#'
    
            seen_pal= {1:s[1]} #Pal length, string
            search_zone = range(3,len(s)+1,2)
    
            # Use Bi-search to attack the search zone.
            #Initialize the seen_pal dict
            low = 0
            high = len(search_zone) - 1
            pal_1 = searchForPal(search_zone[low], s)
            pal_2 = searchForPal(search_zone[high], s)
            if pal_1 != '':
                seen_pal[search_zone[low]] = pal_1
            if pal_2 != '':
                seen_pal[search_zone[high]] = pal_2
    
            while low < high:
                mid = (low + high)/2
                if seen_pal.get(search_zone[mid]) is not None:
                    break
                pal = searchForPal(search_zone[mid], s)
                if pal == '':
                    high = mid
                else:
                    seen_pal[search_zone[mid]] = pal
                    low = mid
            maxT = seen_pal[max(seen_pal.keys())]
            result = ''
            for c in maxT: # O(n)
                if c != '#':
                    result += c
            return result

Log in to reply
 

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