AlgoDaily - Validate Palindrome

Good evening! Here's our prompt for today.

Given a string str, can you write a method that will return True if is a palindrome and False if it is not? If you'll recall, a palindrome is defined as "a word, phrase, or sequence that reads the same backward as forward". For now, assume that we will not have input strings that contain special characters or spaces, so the following examples hold:

1str = 'thisisnotapalindrome'
2is_palindrome = is_palindrome(str)
3# False
4
5str = 'racecar'
6is_palindrome = is_palindrome(str)
7# True

For an extra challenge, try to ignore non-alphanumerical characters. The final solution that we present will handle all edge cases.

Constraints

Length of the given string <= 100000
The string will consist of ASCII characters (some or all)
Expected time complexity : O(n)
Expected space complexity : O(1)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx
​
 
def is_palindrome(s):
    # fill in
    return True
​
​
# print(is_palindrome('A Santa Lived As a Devil At NASA'));
​
​
import unittest
​
​
class Test(unittest.TestCase):
    def test_1(self):
        assert is_palindrome("A Santa Lived As a Devil At NASA") == True
        print(
            "PASSED: assert is_palindrome('A Santa Lived As a Devil At NASA') == True"
        )
​
    def test_2(self):
        assert is_palindrome("gold") == False
        print("PASSED: assert is_palindrome('gold') == False")
​
    def test_3(self):
        assert is_palindrome("a") == True
        print("PASSED: assert is_palindrome('a') == True")
​
    def test_4(self):
        assert is_palindrome("racecar") == True
        print("PASSED: assert is_palindrome('racecar') == True")

Tired of reading? Watch this video explanation!

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's how we would solve this problem...

How do I use this guide?

Build your intuition. Is this statement true or false?

A string is defined as a palindrome if the reversal of the string is equal to the original string.

For example, “toot” is a palindrome, but “boot” is not.

Press true if you believe the statement is correct, or false otherwise.

This is a classic question, and there are multiple ways to solve this. For the sake of learning, let's cover all of them!

Using built-in methods

This would probably be invalid in an actual interview, but you can rely on the built-in String method to accomplish a quick reversal. In Javascript, you can simply call reverse() and in Python, you can call [::-1] You can then compare the reversed string to the original:

xxxxxxxxxx
 
def isPalindrome(s):
    # Calling reverse function
    reversed = s[::-1]
​
    # Checking if both strings are equal or not
    if s == reversed:
        return True
    return False
​
print(isPalindrome("racecar"))

Let's test your knowledge. Could you figure out the right sequence for this list?

What's the order of successfully finding out if a string is a palindrome?

Press the below buttons in the order in which they should occur. Click on them again to un-select.

Options:

Open a while loop to perform while low is less than high
Continue until end of loop and return true
Define two variables: high and low, as 0 and (length of string - 1)
If `string[low]` does not equal `string[high]`, return false. Increment low, decrement high

Try this exercise. Click the correct answer from the options.

What will the following pseudocode do to an input string?

1def reverse_str(str):
2  start = 0
3  end = len(str)-1
4  str_copy = [letter for letter in str]
5  while start < end:
6    temp = str_copy[start]
7    str_copy[start] = str_copy[end]
8    str_copy[end] = temp
9    start += 1
10    end -= 1
11  return "".join(str_copy)

Click the option that best answers the question.

Make a copy
Reverse the string
Swap the first and last letters
Infinite loop

With a while loop:

We can cut down on the number of operations by recognizing that we don't need to do len(str)-1 iterations. Instead of using just one pointer that simply iterates through the string from its end, why not use two?

xxxxxxxxxx
 
def is_palindrome(str):
    left = 0
    right = len(str) - 1
    while left < right:
        if str[left] != str[right]:
            return False
        left += 1
        right -= 1
    return True
​
print(is_palindrome('racecar'))

What we're doing above is specifying two pointers, start and end. start points to the beginning of the string, and end is a pointer to the last character. Taking the example input racecar, as we run through it, these are the comparisons we'll see:

xxxxxxxxxx
 
racecar
^     ^
racecar
 ^   ^
racecar
  ^ ^
racecar
   ^
True

Let's test your knowledge. Click the correct answer from the options.

What is the run time of the following code?

PYTHON

1def reverse_str(str):
2  start = 0
3  end = len(str)-1
4  str_copy = [letter for letter in str]
5  while start < end:
6    temp = str_copy[start]
7    str_copy[start] = str_copy[end]
8    str_copy[end] = temp
9    start += 1
10    end -= 1
11  return "".join(str_copy)

Complexity of Final Solution

Let n be the length of the string. We iterate n/2 times until the left pointer is greater than the right pointer for linear O(n) time complexity, and we use a constant O(1) space for the 2 pointers.

Click the option that best answers the question.

O(log n)
O(n)
O(n log n)
O(n^2)

One Pager Cheat Sheet

You can write a method using O(n) time and O(1) space complexity to check if a given string of length 100000 or less is a palindrome, taking into account non-alphanumerical characters.
The given string is a palindrome if it reads the same forwards as it does backwards.
With built-in methods, you can easily reverse() or [::-1] a String and then compare it to the original to check if it is a palindrome.
By utilizing two variables, low and high, to represent the starting and ending indices of a string to be checked, and using a while loop to compare characters at these indices, we can determine if a string is a palindrome or not.
The code reverses a string by looping over the characters, swapping the characters and keeping track of the start and end indexes using a temp variable, and then joining the characters of the str_copy list to return the reversed string.
We can reduce complexity by using two pointers instead of one and only have to do len(str)/2 iterations of the while loop in order to validate if a string is a palindrome.
Comparing characters of a string with two pointers, start pointing to the beginning and end pointing to the last character, the example input racecar shows us the initial comparisons.
The runtime of the code is O(n), with O(1) space complexity, where n is the length of the string, since it iterates linearly with a constant space overhead.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx
    print("Nice job, 4/4 tests passed!")
 
import re
​
ALPHA_NUMERIC = re.compile("[^a-zA-Z0-9]")
​
​
def is_palindrome(s):
    if not s or s == "":
        return True
    else:
        left = 0
        right = len(s) - 1
​
        while left < right:
            left_char = s[left].lower()
            right_char = s[right].lower()
​
            if is_alpha_num(left_char) and is_alpha_num(right_char):
                if left_char == right_char:
                    left += 1
                    right -= 1
                else:
                    return False
            else:
                if not is_alpha_num(left_char):
                    left += 1
                if not is_alpha_num(right_char):
                    right -= 1
​
        return True
​
​
def is_alpha_num(c):

Great job getting through this. Let's move on.

If you had any problems with this tutorial, check out the main forum thread here.

Constraints

Try to solve this here or in Interactive Mode.

Tired of reading? Watch this video explanation!

Here's how we would solve this problem...

Build your intuition. Is this statement true or false?

Using built-in methods

Let's test your knowledge. Could you figure out the right sequence for this list?

Options:

Try this exercise. Click the correct answer from the options.

Click the option that best answers the question.

With a while loop:

Let's test your knowledge. Click the correct answer from the options.

Complexity of Final Solution

Click the option that best answers the question.

One Pager Cheat Sheet

This is our final solution.

Great job getting through this. Let's move on.

Programming Categories

Popular Lessons