Longest Palindromic Substring

longestPalindromicSubstring.py

#--------- Longest Palindromic Substring------------------

'''
Logic:

    we know that a palindrome can be of even or odd length
    For example "aba" here b is center  and in "abba" center is between 2 "b"s
    In below logic we will be using this knowledge

    Everytime we will make 2 assumptions
    1. Current node is center of the palindrome (odd length)
    2. Just before current node there is a center of palindrome (even length)

    About getPalindrome Function:
        It takes a string and 2 index values as parameters. Lets say one index is left and other index value is right.
        This function see whether characters at given indexes are equal
        1. If equal then left will move one index left and right moves right one index and this will continue till left reaches index 0 or right reaches
           last index of string (because after these conditions we will go out of bound)
        2. If characters are not equal on given indexes then obviously it violates the palindrome condition so we break loop there only
        This function will return left+1 and right indexes where ever loop stops

        example : we pass ("aba",0,2)
            function will see character at index 0 (i.e a) and character at index 2 (i.e a) is equal or not.
            Yes they are equal so now left index will go one left it will become -1 where as right become 3. Left index is less than 0 so loop will break
            we found out that max palindrome is between 0 to 2, So we will return [0,3]. 


    Suppose we are given ("ahafghiihgfabbb"). Lets create a list which will store our result,[]
    We will remember the indexes here

    We start with index 0. 
    It is the first character and alone it is a palindrome, there is nothing to the left of it. So we will go to next index i.e 1.
    We found out max length palindrome till now is "a" so we will update our result list [0,1]
    
    Now lets take index 1
    cases:
        1. If b is center that means characters to the left of it and to the right should be equal.
            We will pass index of left character i.e. 0 and right character i.e 2 to our getPalindrome function.
            From getPalindrome function we will get [0,3]
        2. If center is just before b then we will pass index 0,1 to getPalindrome function
           we will get [0,1]
        
        Now we will see among these two cases and the value stored in result list which is max. (for getting max we are taking differences of indexes)
        So we get maximum of all is case 1, so our result became [0,3]

    index 2
    cases : 
        1. If a is center, we get [2,3]
        2. If center is just before a, we get [2,2]
        max of all is result values only so no changes

    this will continue till index 6. Result values won't change

    index 7
    cases: 
        1. If I is center, we will get [7,8]
        2. If center is just before I, we get [3,11]
        max of all is 2nd case, so we update result to [3,11]

    This will continue till the end
    so our result id ("fghiihgf")        

'''

String = "zzzzzzz2345abbbba5432zzbbababa"

def longestPalindromicSubstring2(string):
    result = [0,1]
    for i in range(1,len(string)):
        odd = getPalindrome(string,i-1,i+1)
        even = getPalindrome(string,i-1,i)
        current = max(odd,even,key = lambda x: x[1]-x[0])
        result = max(current,result,key=lambda x: x[1] - x[0])
    return string[result[0]:result[1]]

def getPalindrome(string,left,right):
    while left >= 0 and right < len(string):
        if string[left] != string[right]:
            break
        left -= 1
        right += 1
    return [left + 1, right]

print(longestPalindromicSubstring2(String))

#-----------------------------------------------------------------
#-----------------------------------------------------------------

'''

For logic go to : https://gist.github.com/jatinsharrma/586fa6eb59a0ee37d10555a61eae60bc

It is similar to that logic, finding all sequences and finding max palindrome among them.

A little difference is that if suppose a string like "abba" is a palindrome we are not disintegrating that string
because we will not find maximum palindrome from its substring

'''

# iterative solution
def longestPalindromicSubstring(String):
    result = ""
    buffer = [String]
    temp = []
    while buffer:
        current = buffer.pop(0)
        if len(current) == 0 : break
        flag = palindrome(current)
        if flag: 
            if len(current) > len(result): result = current
            continue
        if current not in temp:
            temp.append(current)
            buffer.append(current[1:])
            buffer.append(current[:-1])
    return result

# recursive solution
def longestPalindromicSubstring1(String, p_lindrome,memory):
    if len(String) == 1:
        return String if len(String) > len(p_lindrome) else p_lindrome
    if len(String) > len(p_lindrome) and palindrome(String):
        return String
    if String not in memory:
        memory.append(String)
        left = longestPalindromicSubstring1(String[1:],p_lindrome,memory)
        right = longestPalindromicSubstring1(String[:-1],p_lindrome,memory)
        length = [len(p_lindrome),len(left),len(right)]
        if length[1] > length[0]:
            if length[1] >= length[2]:
                p_lindrome = left
        elif length[2] > length [0]:
            p_lindrome = right
    return p_lindrome


# this function see whether given string is palindrome or not
def palindrome(string):
    if len(string) <= 1: return True
    mid = len(string)//2
    flag = True
    for i in range(mid+1):
        if string[i] != string[-(i+1)]:
            flag = False
            break
    return flag

String = "zzzzzzz2345abbbba5432zzbbababa"
print(longestPalindromicSubstring1(String,"",[]))
print(longestPalindromicSubstring(String))