'''Given a string s find and return the longest palindromic substring. Ideally in less than n^3 time'''

def palindrome_string(some_string):
    some_string = some_string.lower()
    '''to_remove = [',', "'", ':', '.', '!', '?', '-', ' ']
    for item in to_remove:
        if item in some_string:
            some_string.replace(item, '')'''# this didnt work for some reason?
    some_string = some_string.replace(' ','')
    some_string = some_string.replace('.','')
    some_string = some_string.replace(',','')
    some_string = some_string.replace("'",'')
    max_substring = False
    for i in range(len(some_string)):
        for j in range(1,len(some_string)):
            if some_string[j] == some_string[i]:
                potential_palindrome = some_string[i:j+1]
                if potential_palindrome == potential_palindrome[::-1] and len(potential_palindrome)>1:
                    if max_substring is False or len(potential_palindrome) > len(max_substring):
                        max_substring = potential_palindrome
    return max_substring
def other_palindrome_test(some_string):
    some_string = some_string.lower()
    some_string = some_string.replace(' ','')
    some_string = some_string.replace('.','')
    some_string = some_string.replace(',','')
    some_string = some_string.replace("'",'')
    for end in range(len(some_string),1,-1): # checks increasingly smaller slices of the string looking for a palindrome
        start = 0 # rests start to first letter after each while loop concludes
        while end <= len(some_string): # checks each slice for palindrome and increments if none found
            test_slice = some_string[start:end+1]
            if test_slice == test_slice[::-1]:
                return test_slice
            else:
                start += 1
                end += 1
    return False

def third_palindrome(some_string):
    some_string = some_string.lower()
    some_string = some_string.replace(' ','')
    some_string = some_string.replace('.','')
    some_string = some_string.replace(',','')
    some_string = some_string.replace("'",'')
    max_palindrome = ''
    for i in range(1,len(some_string)):
        left = i-1
        right = i+1
        while left >=0 and right <= len(some_string)-1 and some_string[left] == some_string[right]:
            right += 1
            left -= 1
            potential_palindrome = some_string[left+1:right]
            if len(potential_palindrome) > len(max_palindrome):
                max_palindrome = potential_palindrome
    if max_palindrome =='':
        return False
    else:
        return max_palindrome

def create_palindrome(random_string):
    pass
    # check for existing longest existing paldinrome
    # ------------------------------------------------------------
    # if a palindrome exists
    # create new blank list equal in length to string
    # set current longest exisiting palindrome to center of new list and remove from string
    # check for next longest palindrome if len is odd split the palindrome and place first half not including
    # middle on left in new list and right half not including middle on right in new list remove characters from string
    # repeat until no palindrome exists.
    # check for and count all duplicates.
    # place equal number of all duplicates on either side of center
    # place any odd characters at end of string
    # -------------------------------------------------------------
    # if no palindrome exists
    # check for and count all duplicates.
    # choose odd count for center
    # place equal number of all duplicates on either side of center
    # place any odd characters at end of string
    # -------------------------------------------------------------
    # return palindrome

#Tests:
print(palindrome_string('racecar') == 'racecar')
print(palindrome_string('ghead') is False)
print(palindrome_string('dddfffgggeeeracecar') == 'racecar')
print(palindrome_string('dfsracecardskjdalskjsk') == 'racecar')
print(palindrome_string('racecarlkajsdlkjadr') == 'racecar')
print(other_palindrome_test('racecar') == 'racecar')
print(other_palindrome_test('ghead') is False)
print(other_palindrome_test('dddfffgggeeeracecar') == 'racecar')
print(other_palindrome_test('dfsracecardskjdalskjsk') == 'racecar')
print(other_palindrome_test('racecarlkajsdlkjadr') == 'racecar')
print(third_palindrome('racecar')== 'racecar')
print(third_palindrome('ghead')is False )
print(third_palindrome('dddfffgggeeeracecar')== 'racecar')
print(third_palindrome('dfsracecardskjdalskjsk')== 'racecar' )
print(third_palindrome('racecarlkajsdlkjadr')== 'racecar')

# sentence tests
print('sentence tests')
print(palindrome_string('Euston saw I was not Sue.') == 'eustonsawiwasnotsue')
print(other_palindrome_test('Euston saw I was not Sue.') == 'eustonsawiwasnotsue')
print(third_palindrome('Euston saw I was not Sue.') == 'eustonsawiwasnotsue')
print(palindrome_string('When I entered, Euston saw I was not Sue.') == 'eustonsawiwasnotsue')
print(other_palindrome_test('When I entered, Euston saw I was not Sue.') == 'eustonsawiwasnotsue')
print(third_palindrome('When I entered, Euston saw I was not Sue.') == 'eustonsawiwasnotsue')
print(palindrome_string('This is not a palindrome') == 'isi')
print(other_palindrome_test('This is not a palindrome') == 'isi')
print(third_palindrome('This is not a palindrome') == 'isi')
print(palindrome_string('Marge let a moody baby doom a telegram.') == 'margeletamoodybabydoomatelegram')
print(other_palindrome_test('Marge let a moody baby doom a telegram.') == 'margeletamoodybabydoomatelegram')
print(third_palindrome('Marge let a moody baby doom a telegram.') == 'margeletamoodybabydoomatelegram')
print(palindrome_string('No I am not your palindrome') is False )
print(other_palindrome_test('No I am not your palindrome') is False)
print(third_palindrome('No I am not your palindrome') is False)
print(palindrome_string('With the days forever darkening, And the signs so very clear,We must keep our sense of urgency,'
                        'As the end is drawing near. We will seize this opportunity To declare Jehovah’s name, '
                        'And the blessings of his Kingdom Is the message we’ll proclaim.') == other_palindrome_test(
    'With the days forever darkening, And the signs so very clear,We must keep our sense of urgency ,As the end is '
    'drawing near. We will seize this opportunity To declare Jehovah’s name, And the blessings of his Kingdom '
    'Is the message we’ll proclaim.') == third_palindrome('With the days forever darkening, And the signs so very clear,We must keep our sense of urgency,'
                                                         'As the end is drawing near. We will seize this opportunity To declare Jehovah’s name, '
                                                         'And the blessings of his Kingdom Is the message we’ll proclaim.'))