Optimize Time/Space Complexity for Solving Palindromes

Question

This problem was recently asked by Twitter:

A palindrome is a sequence of characters that reads the same backwards and forwards. Given a string, s, find the longest palindromic substring in s.

Example:

Input: "banana"
Output: "anana"

Input: "million"
Output: "illi"

class Solution: 
    def longestPalindrome(self, s):
      # Fill this in.
        
# Test program
s = "tracecars"
print(str(Solution().longestPalindrome(s)))
# racecar

So i solved it like that

class Solution: 
    def longestPalindrome(self, s):
        index = 0
        longestPalindrome = ""
        for x  in s:
            subStr = s[index + 1:]
            nextIndex = subStr.find(x)
            while nextIndex != -1:
                txt = x + subStr
                pland = txt[:nextIndex + 2]
                if self.isPalindromicSubString(pland):
                    if len(pland) > len(longestPalindrome):
                        longestPalindrome = pland
                nextIndex = subStr.find(x,nextIndex + 1)
            index = index + 1
        return longestPalindrome

    def isPalindromicSubString(self,subStr):
        index = 0
        reverseIndex = -1
        isItPalindromic = True
        for y in subStr:
            if y != subStr[reverseIndex]:
               isItPalindromic = False
            index = index + 1
            reverseIndex = reverseIndex - 1  
        return isItPalindromic

# Test program
s = "abcdef aka"
print(str(Solution().longestPalindrome(s)))
# racecar

it's works fine and it's time complexity is O(N^2) is there any way to do it better , and give me your comments about both time,space complexity

Answer 1

Turns out you can actually solve this problem using dynamically generated regular expressions.

# Question: https://stackoverflow.com/questions/62838784/optimize-time-space-complexity-for-solving-palindromes

import re
import time


def longestPalindrome(string, longest_first=True):
    palindrome = None
    order = range(len(string)//2, -1, -1) if longest_first else range(1, len(string)//2+1)
    for n in order:
        # Example: re.sub(r'^.*(\w)(\w)(\w)(\w)(\w)?\3\2\1.*$', r'\1\2\3\4\3\2\1', s)
        regex_match = "".join([
            r'^.*',
            r'(\w)' * n,
            r'(\w)?',
            ''.join([ f'\\{i}' for i in range(n,0,-1) ]),
            r'.*$'
        ])
        if re.match(regex_match, string):
            regex_replace = "".join([ f'\\{i}' for i in list(range(1,n+2))+list(range(n,0,-1)) ])
            palindrome    = re.sub(regex_match, regex_replace, string)
            if longest_first:
                return palindrome  # return the first match
        else:
            if not longest_first:
                break  # return the last match

    return palindrome


if __name__ == '__main__':
    for longest_first in [True, False]:
        print(f'\nLongest First = {longest_first}')
        for sentence in [
            "banana",
            "tracecars",
            "detartrated",
            "saippuakivikauppias",
            "this is not the palindrome you are looking for"
        ]:
            start_time = time.perf_counter()
            answer     = longestPalindrome(sentence, longest_first)
            time_taken = time.perf_counter() - start_time
            print(f'len({len(sentence):2d}) in {1000*time_taken:6.2f}ms = longestPalindrome({sentence}, {longest_first}) == {answer}')

    assert longestPalindrome("banana")      == "anana"
    assert longestPalindrome("tracecars")   == "racecar"
    assert longestPalindrome("detartrated") == "detartrated"

Longest First = True
len( 6) in   0.79ms = longestPalindrome(banana, True) == anana
len( 9) in   0.39ms = longestPalindrome(tracecars, True) == racecar
len(11) in   0.41ms = longestPalindrome(detartrated, True) == detartrated
len(19) in   0.59ms = longestPalindrome(saippuakivikauppias, True) == saippuakivikauppias
len(46) in  13.19ms = longestPalindrome(this is not the palindrome you are looking for, True) == oo

Longest First = False
len( 6) in   0.06ms = longestPalindrome(banana, False) == anana
len( 9) in   0.08ms = longestPalindrome(tracecars, False) == racecar
len(11) in   0.19ms = longestPalindrome(detartrated, False) == detartrated
len(19) in   0.46ms = longestPalindrome(saippuakivikauppias, False) == saippuakivikauppias
len(46) in   0.04ms = longestPalindrome(this is not the palindrome you are looking for, False) == oo

There are two algorithm options, one that searches for the longest possible palindrome first then shrinks the regex until it finds a match, the other checks if a 2-char palindrome exists first then keeps growing the regexp until it has found the longest match.

In the longest_first version:

Best case time complexity, for a true palindrome, is O(N) as the regex just needs to loop over the string once to verify.

Worst case time complexity is for a non-palindrome. The main loop will run N/2 times. Regexp time complexity on the first loop will need to read half the string to exclude, then on the second loop check two combinations of positions: O(N/2) + O(2*(N/2-1)), O(3*(N/2-2)) and so on. Wolfram Alpha says this is O(N^3/48 + N^2/8 + N/6) ~= (N/3)^3 + (N/3)^2. So overall time complexity is about O((N/4)^4).

• https://www.wolframalpha.com/input/?i=sum+%28m+*+%28N%2F2-%28m-1%29%29%29+for+m+%3D+1...N%2F2.

However, even for short sentences, actual execution time is still in the millisecond range, which may be fast enough not to have to worry about it.

Shortest First

If you change the assumption to be that most inputs will not be palindromes, then it may be quicker to test if a palindrome of length 2 exists before incrementally expanding to larger substrings. This is a tradeoff between best and worst case time complexity. Non-palindromes can be excluded quickly, but long palindromes will take a bit of extra time.

Answer 2

Here is a python implementation of Manacher's Algorithm, from the Wikipedia article linked by Kevin

def longest_palindrome_substring(s: str) -> str:
    # Add sentinel chars between chars of s and around s, to handle even length palindromes
    # Different outer chars to exit palindrome expanding loop without boundary checking
    # in case the entire string is a palindrome
    with_boundaries = "@|" + "|".join(s) + "|!"

    # Length of palindrome centered at each index in the new string
    palindrome_lengths = [0 for _ in with_boundaries]

    # Center of current palindrome
    center_current = 0
    # Right boundary of current palindrome
    right_current = 0

    # Track largest palindrome length and center index
    max_len = 0
    max_center = 0
    for i in range(2, len(with_boundaries) - 2):
        # If i is inside a bigger palindrome, copy the length of the mirror palindrome
        # e.g. *abacaba*
        #            ^  the second aba inside abacaba must have the same length of the first
        if i < right_current:
            center_mirror = 2 * center_current - i
            # add only the length of the mirror palindrome inside the current one
            palindrome_lengths[i] = min(right_current - i, palindrome_lengths[center_mirror])

        # Increase the length of the palindrome from the center
        while (
            with_boundaries[i + palindrome_lengths[i] + 1]
            == with_boundaries[i - (palindrome_lengths[i] + 1)]
        ):
            palindrome_lengths[i] += 1

        # Update current right boundary and current center index
        if i + palindrome_lengths[i] > right_current:
            right_current = i + palindrome_lengths[i]
            center_current = i

        # Keep track of the longest
        if palindrome_lengths[i] > max_len:
            max_len = palindrome_lengths[i]
            max_center = i
    # return from max_center - max_len to max_center + max_len, filtering out sentinel chars
    return "".join(
        c
        for c in with_boundaries[max_center - max_len : max_center + max_len + 1]
        if c not in "@|!"
    )

While it does seem to have quadratic complexity O(n^2), having a while loop inside a for loop, it actually is only O(n), as explained on wikipedia

Answer 3

First, I don't know why are you using clas for this. We in python do not write classes if do not use OOP, which you are not

Intro

I went through middles of would be palindrome substrings *1,
and from that middle went left until substring was no longer palindrome
or end of the string was met

code

def find_longest_p(s):
    pal_start = 0; pal_end = 1 # indexes of longest
    for half_index in range(0, len(s)*2-1):
        # about 1st range bounds
        # it goes over middles of palindromes
        # which are at some char or between 2 chars
        # that char is s[half_index/2]
        #    where for odd it is s[x.5] meaning between s[x] a& s[x+1]
        
        c = b = -1 # start with value because for else is asking for b,c
        
        for b in range((half_index + half_index % 2) // 2 - 1, -1, -1):
            # starts from first index to the left, goes to 0
            # "a b c d" (str "abcd", disregard spaces)
            #  0123456  (half indexes)
            # for half_index == 4
            #    b goes -> 1 -> 0
            # for half_index == 3
            #    b goes -> 1 -> 0
            
            c = half_index - b # symetric index of b
            if c < len(s) and s[b] == s[c]: # if not, either end of string or no longer palindrome
                continue
            lenght = c - b - 1
            if lenght > pal_end - pal_start:
                pal_start = b + 1
                pal_end = c
            break
        else:
            # out of bounds to the left
            # arithmetic changes a little
            lenght = c - b + 1
            if lenght > pal_end - pal_start:
                pal_start = b
                pal_end = c + 1
    return s[pal_start : pal_end]

complexity

It seems that this has O(n^2)
which is not actually the case, since, in an average string, not much of palindromes are found.
meaning the 2nd loop mostly has a single iteration
taking O(n) time complexity,
and additional O(1) space, defining 3 variables, and some middle products,
or O(n) space if you include copying and slicing s (that is inevitable)

Footnotes

*1 middle of palindrome can be at some index or in between two indexes
therefore, I went through double indexes
middles would be: 0, 0.5, 1, 1.5, ...
I went: 0, 1, 2, 3, ...