Finding Palindromes

A palindrome is a number, phrase, word, or text that reads the same forwards and backwards.

For example: “level”, “radar”, “rotator”.

During interviews, especially in live coding sessions, candidates are often asked to write a simple method to find palindrome words.

Here’s an example of such a method:

def palindrome(*, a: str) -> bool:
    return a == a[::-1]

Example usage:

>>> palindrome(a="mirror")
>>> False
>>> palindrome(a="level")
>>> True

In Python, the expression a[::-1] is used to get a reversed copy of a list or string. This is a slicing technique where:

a is the list or string to be sliced.

: is the slicing syntax (leaving the start and end empty means the entire string or list is taken).

-1 is the step (a negative step reverses the order).

a[::-1] creates a new string or list containing the same elements as the original, but in reverse order.

There’s another way to solve this problem:

def palindrome(*, a: str) -> bool:
    for i in range(len(a) // 2):
    	if x[i] != x[-i]:
            return False
    return True

The idea is to loop up to half the length of the word and compare characters from the beginning with those from the end using slicing: : a[i] != a[-i-1].

Let's make it a little bit more complicated

The input will not be 1 word, but a whole phrase.

For example: No lemon, no melon!

In this case we have to cut off the occurrences of punctuation marks and spaces, sometimes numbers are allowed. Again, we can try to solve our problem in several ways

import re

def palindrome_1(*, a: str) -> bool:
	cleaned_data = re.sub(r'[^a-zA-Z0-9]', '', a).lower()
    return cleaned_data == cleaned_data[::-1]

Explanation of palindrome_1

It's the same as the previous method, except that it uses a regular expression:

re.sub() — use this function to replace substrings in accordance with the template.
r'[^a-zA-Z0-9] — regular expression (pattern), means «any character that is not a letter or number».
'' is the second part of re.sub(). This is what you replace it with.
a — the line where the replacement will be performed.
lower() — convert the result to lower case

And then there's the now-familiar test.

Time complexity: O(n)

Spatial complexity: O(n)

def palindrome_2(*, a: str) -> bool:
    new_str = ''
        for item in a:
            if item.isalnum():
                new_str += item.lower()
        return new_str == new_str[::-1]

Explanation of palindrome_2

Here we decided to take a different approach. We'll use the isalnum() method to check whether the characters in the string are letters or numbers.

We will also use the new_str variable to store the resulting string. Note that this variable will be constantly updated (recreated), since strings are an immutable data type. We will constantly create a new string in a loop, copying the contents of new_str and adding a new character.

Since this is done inside a loop, the total complexity of this part can be O(n^2). However, Python interpreters often optimize this operation using amortized analysis. In practice, if the strings are small, the performance differences with O(n) solution may be negligible.

Temporal complexity

Officially O(n^2), but in practice it is often closer to O(n) due to interpreter optimizations. It is important to remember the potential quadratic complexity if the code will be handling very large strings. This should be kept in mind when proposing this solution.

Spatial complexity: O(n)

What if I told you that there is another way to solve this problem with time complexity O(n) and space complexity O(1)? Not only that, but you don't have to use regular expressions.

def palindrome_3(*, a: str) -> bool:
        l, r = 0, len(a) - 1

        while l < r:
            while l < r and not is_alpnum(ch=a[l]):
                l += 1
            while r > l and not is_alpnum(ch=a[r]):
                r -= 1
            if a[l].lower() != a[r].lower():
                return False
            l, r = l + 1, r - 1
        return True
    
def is_alpnum(*, ch):
    return ord('A') <= ord(ch) <= ord('Z') or ord('a') <= ord(ch) <= ord('z') or ord('0') <= ord(ch) <= ord('9')

Looks complicated? Let's figure it out

Explanation of palindrome_3

For convenience, we have implemented is_alpnum() function. It checks if the character ch is an alphanumeric character (a letter of the Latin alphabet or a digit).

ord(ch) — returns the Unicode code of ch character. That means we check if the character ch is in the range of uppercase letters, in the range of lowercase letters, and in the range of digits.

How palindrome_3 main function works:

l, r = 0, len(a) — 1 — initialize two pointers: l (left) at the beginning of the string and r (right) at the end of the string.
while l < r: — main loop that will continue until the left-hand pointer crosses the right-hand pointer.
while l < r and not is_alpnum(ch=a[l]): l += 1— move the left pointer to the right until an alphanumeric character is found. not is_alpnum(ch=a[l]) checks that the character is not alphanumeric.
while r > l and not is_alpnum(ch=a[r]): r -= 1 — move the right pointer to the left until we find an alphanumeric character.
if a[l].lower() != a[r].lower(): return False — if the characters pointed to by l and r (reduced to lowercase) are not the same, the string is not a palindrome and the function returns False.
l, r = l + 1, r - 1 — move the left pointer to the right and the right pointer to the left.
return True — the string is a palindrome and the function returns True if the loop has completed without finding any mismatches.