Find The Palindrome Of A String By Using Python

I would like to find the longest palindrome from a given string. then print it lines = 'forgeeksskeegfor' length = len(lines) a = [lines[i:j+1] for i in range(length) for j in rang

Solution 1:

There are two palindrome scenarios: Even palindromes (e.g. noon) and Odd palindromes (e.g. radar). There are only two possible (longest) palindromes for each position in the string. So, for each position, you only need to find the longest Even and Odd palindromes centred at that position by comparing characters forward and back.

s = "forgeeksskeegfor"from os import path 
longest = ""for i inrange(1,len(s)-1):
    ifmin(i,len(s)-i)*2+1 <= len(longest): continuefor odd in [1,0]:
        if s[i+odd] != s[i-1]: continue
        halfSize = len(path.commonprefix([s[i+odd:],s[:i][::-1]])) 
        if2*halfSize + odd > len(longest):
            longest = s[i-halfSize:i+halfSize+odd];breakprint(longest) # geeksskeeg

Note: this could be further optimized but will respond in O(n) time most of the time or up to O(n^2/2) in the worst case scenario where the string contains very long chains of identical characters (or only a single repeated character)

UPDATE

In order to minimize the impact of long chains of identical characters, the order of center positions for potential palindromes could follow a binary search pattern. The binRange() generator below can be used to replace range(1,len(s)-1) with binRange(1,len(s)-1) in the main loop. This will ensure that longer palindromes are found early and shorter embedded ones can be short circuited in subsequent iterations.

from itertools import zip_longest
defbinRange(lo,hi=None):
    if hi isNone: lo,hi = 0,lo
    if hi <= lo: return
    mid = (lo+hi-1)//2yield mid
    for a,b in zip_longest(binRange(lo,mid),binRange(mid+1,hi),fillvalue=None):
        if a isnotNone: yield a
        if b isnotNone: yield b

Solution 2:

instead of looking for max of a list of 'strings' , you should look for maximum length. based on your approach.

lines = "forgeeksskeegfor"
length = len(lines)
a = [lines[i:j+1] for i in range(length) for j in range(i, length)]

total = []
forstringin a:
    ifstring == string[::-1]:
        total.append(string)
max_len = max( [ len(x) for x in total ] )
# result list will contain the longest pallindroms
result_list = [ x for x in total iflen(x) == max_len ]

There is some flaw in your palindrome check.

forstring in a:
    # the below line will not change anything# you are just converting a string to list on the fly # reversing it ,but not storing it somewherelist(string).reverse()
    # string is still string of a , and reverse_String and string# both will be same.
    reverse_String = "".join(string)

    # not sure why are you converting to lower hereif reverse_String == string.lower():
      total.append(reverse_String)Hope it helps

Hope it helps.

Solution 3:

This can be solved with dynamic programming

The following code has a worst running time of 2^n when there is no palindrome in the string, so it will try all possible solutions. But its performance increases as it finds a palindrome.

deffind_pal(string, start, end):
    # base caseifend - start <= 1:
        return (start, end)
    # if a palindrome shows:
    elif string[start] == string[end]:
        # check if its substring is a palindrome also
        next_pal = find_pal(string, start + 1, end - 1)
        if next_pal == (start + 1, end - 1):
            # if it is, then return the longerreturn (start, end)
        else:# if it is not, still return any smaller palindrome in stringreturn next_pal
    else:# if this string is not a palindrome, check for a smaller in a  substring
        next_pal1 = find_pal(string, start + 0, end - 1)
        next_pal2 = find_pal(string, start + 1, end - 0)
        if next_pal1[1] - next_pal1[0] > next_pal2[1] - next_pal2[0]:
            return next_pal1
        else:return next_pal2


deffind_greatest_pal(string):
    pal_pair = find_pal(string, 0, len(string)-1)
    return string[pal_pair[0]:pal_pair[1]+1]


print(find_greatest_pal("forgeeksskeegfor"))

Solution 4:

The idea is to iterate through the string and generate all palindromes starting from the center and moving out to the two sides. If we find a palindrome greater than our current length, we replace it with the new one.

deflongestPalindrome(s):
    ans = ""for i inrange(len(s)):
        for k inrange(2):
            temp = helper(s, i, i + k)
            iflen(temp) > len(ans):
                ans = temp
    return ans

defhelper(s, l, r):
    while l >= 0and r < len(s) and s[r] == s[l]:
        l -= 1
        r += 1return s[l+1:r]

Usage:

print(longestPalindrome('forgeeksskeegfor'))
geeksskeeg

Solution 5:

There is a simple way, this function can help you:

deflongest_palindrome(text):
    text = text.lower()
    longest = ""for i inrange(len(text)):
        for j inrange(0, i):
            chunk = text[j:i + 1]
            if chunk == chunk[::-1]:
                iflen(chunk) > len(longest):
                    longest = chunk
    return longest


print(longest_palindrome("forgeeksskeegfor"))