Deciding whether a string is a palindrome

Question

This is a python question. Answer should be with O(n) time complexity and use no additional memory. As input i get a string which should be classified as palindrome or not (palindrome is as word or a phrase that can be read the same from left to right and from right to left, f.e "level"). In the input there can be punctuation marks and gaps between words. For example "I. did,,, did I????" The main goal is to decide whether the input is a palindrome.

When I tried to solve this question i faced several challenges. When I try to delete non letter digits

for element in string:
    if ord(element) not in range(97, 122):
        string.remove(element)
    if ord(element) == 32:
        string.remove(element)

I use O(n^2) complexity, because for every element in the string i use remove function, which itself has O(n) complexity, where n is the length of the list. I need help optimizing the part with eliminating non letter characters with O(n) complexity

Also, when we get rid of spaces as punctuation marks I know how to check whether a word is a palindrome, but my method uses additional memory.

Answer 1

Here is your O(n) solution without creating a new string:

def is_palindrome(string):
    left = 0
    right = len(string) - 1

    while left < right:
        if not string[left].isalpha():
            left += 1
            continue
        if not string[right].isalpha():
            right -= 1
            continue

        if string[left] != string[right]:
            return False

        left += 1
        right -= 1

    return True


print(is_palindrome("I. did,,, did I????"))

Output:

True