[Interview Question] How to Check a Valid Palindrome?

[toc]

Company tags: Apple, Amazon, Bloomberg, Facebook, Microsoft, Oracle

This is one of the most commonly occurred questions in numerous interviews and you should be absolutely ready to solve this question in a flash as soon as you see this in your interview. Hence, let’s dive into the problem and solution to this interview question.

Problem Statement

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

⚠️Constraints:

1 <= s.length <= 2 * 10⁵
s consists only of printable ASCII characters.

Examples

Let us look at some examples to improve the understanding of the problem:

Example 1:
Input: s = “A man, a plan, a canal: Panama”
Output: True
Explanation: “amanaplanacanalpanama” is a palindrome.

Example 2:
Input: s = “race a car”
Output: False
Explanation: “raceacar” is not a palindrome.

Example 3:
Input: s = “Red rum, sir, is murder”
Output: True
Explanation: “redrumsirismurder” is a palindrome.

Example 4:
Input: s = “Abc def, ghi jklm.”
Output: False
Explanation: “abcdefghijklm” is not a palindrome.

Example 5:
Input: s = “11 aa 2, 32 aa11”
Output: True
Explanation: “11aa232aa11” is a palindrome.

Now that you have a clear understanding of the problem, let’s dive into various methods to solve the problem:

Method 1: Using Slicing

Approach: The most basic approach to check whether the given string is a valid palindrome or not is to compare the original string with the reversed string. You can reverse the given string with help of slicing. Remember to eliminate the characters that are not alphanumeric before using the slice operation on the string. Return true if the original string and the reversed string are equal. Otherwise, return false.

? A Quick Recap to Slicing in Python
Slicing is a Python concept to carve out a substring from a given string s by using the square bracket notation s[start:stop:step] specifying the start index, the stop index, and the step size. You can set default start and stop indices and use negative step size -1 to reverse a given string in Python. The respective code would be s[::-1] to reverse string s.

Algorithm:

Initialize an empty string that will store only the alphanumeric characters of the original string.
For every character in the string, check whether it is alphanumeric. If yes, add the lowercase character to the new string.
Compare the reversed string with the original string. If equal return True, else returns False.

Solution:

def valid_palindrome(s):
    new_s = ''
    for c in s:
        if c.isalnum():
            new_s = new_s + c.lower()
   
    if new_s[::-1] == new_s:
        return True
    else:
        return False

? isalnum() in Python:
The alphanumeric characters are all the alphabets (A to Z) and numbers (0- 9). All the other characters including- spaces, ?! are not considered as alphanumeric characters. The isalnum() is a built-in function in Python that returns true when the characters are alphanumeric; else it returns false.

Syntax:
s.isalnum()

? Negative Slicing in Python: This is an interesting feature in Python. A negative step size indicates that we are not slicing from left to right, but from right to left. Hence, the start index should be larger or equal than the end index (otherwise, the resulting sequence is empty). e.g. s[5:1:-1]

? Related Question: What are the default indices when using a negative step size (e.g. s[::-1])? In this case, the default indices are not start=0 and end=len(s) but the other way round: start=len(s)-1 and end=-1. Note that the start index is still included and the end index still excluded from the slice. Because of that, the default end index is -1 and not 0.

Test Case Analysis: Let’s run the above code on our examples:

# Example 1
s = “A man, a plan, a canal: Panama”
print(valid_palindrome(s))
# True

# Example 2
s = “race a car”
print(valid_palindrome(s))
# False

# Example 3
s = “Red rum, sir, is murder”
print(valid_palindrome(s))
# True

# Example 4
s = ” Abc def, ghi jklm.”
print(valid_palindrome(s))
# False

# Example 5
s = “11 aa 2 32 aa11”
print(valid_palindrome(s))
# True

Yeah! It passed all the test cases.

Complexity Analysis:

Time Complexity: The time complexity of this method is O(n), as we have traversed the string linearly only once.
Space Complexity: The space complexity of this method is O(n) as extra space is used to store the reversed string.

Method 2: Using Two Pointers

Approach: In this approach, we will use two pointers- one at the start and another at the end of the string to check whether the string is a valid palindrome. The two-pointer approach helps to save the extra memory used in the previous method.

Algorithm:

Initialize two pointers start and end at the start and end of the string.
Keep checking if the character at both the pointers is alphanumeric till the value of the start pointer is less than the value of the end.
If the characters at both the start and end pointers are alphanumeric, check if both the characters are the same. (Use lower() to ignore the case)
If the characters are not equal, return False.
If the loop ends, it implies the string is a valid palindrome, hence return True.

The following illustration demonstrates the working principle of the above algorithm. The gven string in this case is “1,M om 1“.

Solution:

def valid_palindrome(s):
    start = 0
    end = len(s) - 1
    while start < end:
        while start < end and not s[start].isalnum():
            start = start + 1
        while start < end and not s[end].isalnum():
            end = end - 1
        if s[start].lower() != s[end].lower():
            return False

        start = start + 1
        end = end - 1
    	
    return True

Test Case Analysis: Let’s run this on our examples.

Yeah! It passed all the test cases.

Complexity Analysis:

Time Complexity: The time complexity of this method is O(n) as we visit every character of the string only once.
Space Complexity: The space complexity of this method is O(1), as no extra space gets used.

Method 3: Using Regular Expressions

Approach: This method is the most Pythonic way you can use to solve the problem. Import the Python built-in package re to check whether the string is a valid palindrome.

import re

Reg-ex module in Python: To work with regular expressions, Python has a built-in module called regex module. There are various functions in this module that can be used on the strings.

To check if the string is a valid palindrome, you have to use re.sub() on a set of alphanumeric characters that need to be replaced with its lowercase character.

Do you want to master the regex superpower? Check out the new book The Smartest Way to Learn Regular Expressions in Python with the innovative 3-step approach for active learning:
(1) study a book chapter,
(2) solve a code puzzle, and
(3) watch an educational chapter video.

Solution:

import re
def valid_palindrome(s):
    s = re.sub('[^0-9a-zA-Z]', '', s.lower())

    if s[::-1] == s:
        return True
    else:
        return False

Test Case Analysis: Let’s run this on our examples.

Yeah! It passed all the test cases.

Complexity Analysis: The time complexity of this method is O(n) as we visit every character of the string only once.

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

?‍? Post Credits: Shubham Sayon and Rashi Agarwal

Recommended: Finxter Computer Science Academy

One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
So, do you want to master the art of web scraping using Python’s BeautifulSoup?
If the answer is yes – this course will take you from beginner to expert in Web Scraping.