CODEWITHSUNDEEP
pythonalgorithm
Sam
Sam

Reputation: 551

Longest palindrome substring algorithm not working properly for even palindromes

The algorithm I wrote in Python seems to be working fine when it comes to extracting longest palindromes that have even number of characters but not for their odd counterparts:

some_input_2 = "abdbaabeeba"
size_of_some_input_2 = len(some_input_2)
max = 0
final_max = 0
idx_center_letter = 0
final_idx_center_letter = 0
for j in range(2):
    for idx, letter in enumerate(some_input_2):
        i = 0
        while i <= int(size_of_some_input_2 / 2) + 1 and not idx - i < 0 and not idx + i+j >= size_of_some_input_2:
            upper_idx = idx + i +j
            bottom_idx = idx - i
            if some_input_2[bottom_idx] == some_input_2[upper_idx]:
                i = i + 1
            else:
                break
        if max < i :
            max = i #-j
            idx_center_letter = idx + 1

    if final_max <= max:
        final_max = max
        final_idx_center_letter = idx_center_letter
        print(max)
        print(idx_center_letter)
print(some_input_2[final_idx_center_letter - final_max:final_idx_center_letter + final_max])

here the even palindrome abdbaa is the output which is wrong. If the input was some_input_2 = "abbaabeeba" then the output would be abeeba which is correct. Any idea what is wrong here?

Upvotes: -2

Views: 102

Answers (3)

PkDrew
PkDrew

Reputation: 1171

I did a solution using same logic as you wanted:

some_input_2 = "abdbaa"
size_of_some_input_2 = len(some_input_2)

# Variables to track the longest palindrome
final_length = 0
final_start = 0

# Function to expand around a potential center
def expand_around_center(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    # Return the start index and length of the palindrome
    return left + 1, right - left - 1

# Iterate over each character to find palindromes
for idx in range(size_of_some_input_2):
    # Odd-length palindrome (single character center)
    start, length = expand_around_center(some_input_2, idx, idx)
    if length > final_length:
        final_length = length
        final_start = start
    
    # Even-length palindrome (two-character center)
    start, length = expand_around_center(some_input_2, idx, idx + 1)
    if length > final_length:
        final_length = length
        final_start = start

# Extract the longest palindromic substring
longest_palindrome = some_input_2[final_start:final_start + final_length]
print("Longest Palindromic Substring:", longest_palindrome)

Besides the bugs that @btilly already pointed out, there yet lies a significant one: in the very last line of your code:

print(some_input_2[final_idx_center_letter - final_max:final_idx_center_letter + final_max])

Python's string slicing has close interval at left side but open interval at right, so what you want is actually:

print(some_input_2[...: final_idx_center_letter + final_max + 1])

N.B. If you were looking for an optimal yet common solution, the name is Manacher algorithm, which addresses the longest palindromic substr task in O(n) complexity.

The core of Manacher algorithm is you can copy the longest palindromic info of already examined part and paste it to its mirror of not yet examined part, provided that the mismatch itself can be also mirrored. i.e., the mismatch must occur within the mirrored length. And an augmented string is used to unify even and odd length scenario.

Upvotes: 1

Adon Bilivit
Adon Bilivit

Reputation: 27201

Your algorithm is over-complicated. This will handle both odd and even length strings:

def ispalindrome(s: str) -> bool:
    return s == s[::-1]

def longest_palindrome_substring(s: str) -> str:    
    start, size = 0, 1

    for i in range(1, len(s)):
        left = i - size
        right = i + 1

        if left > 0 and ispalindrome(s[left-1:right]):
            size += 2
            start = left - 1
        elif ispalindrome(s[left:right]):
            size += 1
            start = left

    return s[start:start+size]

print(longest_palindrome_substring("abdbaabeeba"))

Upvotes: 0

btilly
btilly

Reputation: 46497

First bug:

        if max < i :
            max = i #-j
            idx_center_letter = idx + 1

You should have j be part of that calculation.

Key bug: You are trying to figure out the palindrome from max and idx_center_letter only. Which means that you've lost all record of the role of j in finding it.

What you need to do is save the upper_idx and bottom_idx that are part of your best found palindrome. That way you'll be able to reconstruct it accurately. And use them to calculate your max.

Tip. max is a built-in function, which makes it a poor choice of variable name. Reviewers will expect the normal name. I would personally choose a descriptive name like best_len, with associated best_upper_idx and best_lower_idx.

Upvotes: 1

Related Questions