Wild Palindrome Hunt

2021-10-26.py

question = """

Given a string s where some of the letters can be “wilds” (denoted by an underscore _),
find the longest palindrome possible from the letters of s in order, where the wilds 
can be any character.

Example:

$ longestPalindrome('abcb_cbcbafg')
$ 'abcbccbcba'

$ longestPalindrome('xyzi_iizy')
$ 'yziiiizy'

"""

import re

# from 2021-08-16: Palindrom Hunt

def palTest(pal, str):
    pal_double = re.compile(r'((.)' + pal + r'(\2))')
    pal_single = re.compile(r'((.)' + pal + r'(\2))')
    double_test = pal_double.search(str)
    if double_test:
        if str == pal:
            print('equal')
            return double_test.group(1)
        else:
            return double_test.group(1)

    else:
        single_test = pal_single.search(str)
        if single_test:
            print('single')
            return single_test.group(1)
        else:
            return False

def pSubstring(input):
    pals = {}

    out = palTest('', input)

    # start with double center
    while out:
        next = palTest(out, input)
        if out == input:
            break
        if next:
            out = next
        else:
            break
    if out:
        pals[out] = 1

    for char in input:
        out = palTest(char, input)
        if out:
            pals[out] = 1

    for pal in pals.keys():
        return(pal)

def longestPalindrome(input):
    letters ='abcdefghijklmnopqrstuvwxyz'
    longest_palindrome = ''
    for letter in letters:
        test_input = re.sub(r'_', letter, input)
        output = pSubstring(test_input)
        if output:
            if len(output) > len(longest_palindrome):
                longest_palindrome = output
    return longest_palindrome

print(longestPalindrome('abcb_cbcbafg'))
print(longestPalindrome('xyzi_iizy'))