'''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('.','')
    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]
                #print(potential_palindrome ,potential_palindrome[::-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('.','')
    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
#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')

# 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(palindrome_string('This is not a palindrome') == 'isi')
print(other_palindrome_test('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(palindrome_string('No I am not your palindrome') is False )
print(other_palindrome_test('No I am not your palindrome') is False)