Python Algorithms

Question

Anyone knows how to solve this question or have any other solutions to solve this question in Python? Develop a program in Python to find the top longest palindromes from a input string.

Currently my code is only able to print out a single longest palindrome:

import sys 
# A utility function to print a
# substring str[low..high]
def printSubStr(st, low, high) :
    sys.stdout.write(st[low : high + 1])
    sys.stdout.flush()
    return ''
 
# This function prints the longest palindrome substring of st[]. It also returns the length of the longest palindrome
def longestPalSubstr(st) :
    n = len(st) # get length of input string
    # table[i][j] will be false if substring
    # str[i..j] is not palindrome. Else
    # table[i][j] will be true
    table = [[0 for x in range(n)] for y
                          in range(n)]
     
    # All substrings of length 1 are palindromes
    maxLength = 1
    i = 0
    while (i < n) :
        table[i][i] = True
        i = i + 1
     
    # check for sub-string of length 2.
    start = 0
    i = 0
    while i < n - 1 :
        if (st[i] == st[i + 1]) :
            table[i][i + 1] = True
            start = i
            maxLength = 2
        i = i + 1
     
    # Check for lengths greater than 2.
    # k is length of substring
    k = 3
    while k <= n :
        # Fix the starting index
        i = 0
        while i < (n - k + 1) :
             
            # Get the ending index of substring from starting index i and length k
            j = i + k - 1
     
            # checking for sub-string from ith index to jth index if st[i + 1] to st[(j-1)] is a palindrome
            if (table[i + 1][j - 1] and
                      st[i] == st[j]) :
                table[i][j] = True
     
                if (k > maxLength) :
                    start = i
                    maxLength = k
            i = i + 1
        k = k + 1
    print("Longest palindrome substring is: ")
    print(printSubStr(st, start,start + maxLength - 1))
 
    return maxLength # return length of LPS

#driver code
st = "agiaehajg32123agaajgak12345654321sasbbqwertytrewqgaga"
l = longestPalSubstr(st)
print("Length is:\n", l)

Can you call longestPalSubstr then remove what is found from st? You can then call longestPalSubstr again as many times as you like. — Fiddling Bits
– Fiddling Bits, Commented Aug 17, 2022 at 15:52
@FiddlingBits how would that work? aabbaad is a counter example — Abhinav Mathur
– Abhinav Mathur, Commented Aug 17, 2022 at 15:57
st = "agiaehajg32123agaajgak12345654321sasbbqwertytrewqgaga"; pos = st.find("qwertytrewq"); st = st[:pos] + st[pos+len("qwertytrewq"):] — Fiddling Bits
– Fiddling Bits, Commented Aug 17, 2022 at 16:04
or do you guys have any better solutions to solve this? thanks ! — Ken Tan
– Ken Tan, Commented Aug 17, 2022 at 16:04

dan04 · Accepted Answer · 2022-08-17 16:17:29Z

1

Here's a straightforward (although not necessarily optimal) algorithm for finding all of the palindromic substrings within a string. It just iterates through all the substrings and saves the ones that are palindromes.

def get_palindromes(s):
    """
    Return a set of all palindromic substrings of s.
    """
    result = set()
    # Iterate through all possible non-empty substrings
    for start in range(len(s)):
       for end in range(start + 1, len(s) + 1):
           substring = s[start:end]
           # Is substring a palindrome?
           if substring == substring[::-1]:
               result.add(substring)
    return result

The output on your test string is:

>>> get_palindromes('agiaehajg32123agaajgak12345654321sasbbqwertytrewqgaga\\')
{'a', 'g', 's', 'gag', 'ertytre', '2', 'bb', 'k', 'sas', 'w', 't', 'q', 'y', 'r', 'h', 'b', '565', '\\', '1', 'j', 'i', 'e', '45654', '32123', '12345654321', 'wertytrew', 'rtytr', 'aga', 'qwertytrewq', '5', '234565432', 'aa', '3', '6', '4', 'tyt', '3456543', '212'}

Now, you just need to sort these values by length, take the 3 longest ones, find them again within the original string, and print each palindrome, index, and length.

answered Aug 17, 2022 at 16:17

dan04

92k23 gold badges169 silver badges206 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Abhinav Mathur Over a year ago

Extremely inefficient though. Will definitely time out for slightly larger strings.

dan04 Over a year ago

@AbhinavMathur: Yes, my code does have O(n²) running time, and will noticeably lag for multi-kilobyte strings. It works fine for OP's 54-character input, though.

Abhinav Mathur · Accepted Answer · 2022-08-17 16:04:59Z

0

Instead of using maxLength, use a minimum heap maxLengths to store the k maximum lengths encountered till now (k=3 for your example).

Try replacing this:

if (k > maxLength) :
    start = i
    maxLength = k

With something like

# maxLengths is being used as a min heap
maxLengths.push((k, start))
if len(maxLengths) > 3:
    maxLengths.pop()

answered Aug 17, 2022 at 16:04

Abhinav Mathur

8,2363 gold badges14 silver badges26 bronze badges

Comments

Crapicus · Accepted Answer · 2022-08-17 17:33:34Z

0

This uses a list comprehension to get all odd length substrings and then searches them for palindrome with the is_palindrome function building a list of results. Finally the results are sorted and displayed.

EDIT: Added deduping of "sub palindromes" re: Ken's comment. EDIT2: Allow even length palindromes

input_str = "agiaehajg32123agaajgak12345654321sasbbqwertytrewqgaga\\"


def is_palendrome(string):
    return string == string[::-1]


subs = [input_str[i: j] for i in range(len(input_str))
        for j in range(len(input_str) + 1, i, -1)]

results = []
for sub in subs:
    if is_palendrome(sub) and not any(sub in result['str'] for result in results):
      results.append({'str': sub, 'idx': input_str.index(sub), 'len': len(sub)})
results = sorted(results, key=lambda x: x['len'])[-3::]
for line in results:
    print(f"Palindrome: {line['str']}, Index: {line['idx']}, Length: {line['len']}")

edited Aug 17, 2022 at 17:33

answered Aug 17, 2022 at 16:18

Crapicus

3231 gold badge2 silver badges9 bronze badges

2 Comments

dan04 Over a year ago

Why only odd lengths, though?

Ken Tan Over a year ago

Saw the update thanks ! However, if u type "cbbd" and it will return "d", instead of "bb". Another example is "aabbaad". I think it will have bug for "two repeating value". Do you have any ideas on this?

Collectives™ on Stack Overflow

Python Algorithms

3 Answers 3

2 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related