Educative: Interactive Courses for Software Developers

Statement#

Write a function that takes a string, s, as an input and determines whether or not it is a palindrome.

Note: A palindrome is a word, phrase, or sequence of characters that reads the same backward as forward.

Constraints:

$1 \leq$ s.length $\leq 2 \times 10^5$
The string s will contain English uppercase and lowercase letters, digits, and spaces.

Solution#

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

The naive approach to solve this problem is to reverse the string and then compare the reversed string with the original string. If they match, the original string is a valid palindrome. Although this solution has a linear time complexity, it requires extra space to store the reversed string, making it less efficient in terms of space complexity. Therefore, we can use an optimized approach to save extra space.

Optimized approach using two pointers#

A palindrome is a word or phrase that reads the same way when it is reversed. This means that the characters at both ends of the word or phrase should be exactly the same.

The two-pointers approach would allow us to solve this problem in linear time, without any additional space complexity or the use of built-in functions. This is because we’ll traverse the array from the start and the end simultaneously to reach the middle of the string.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction#

We’ll have two pointers, where the first pointer is at the starting element of our string, while the second pointer is at the end of the string. We move the two pointers towards the middle of the string and, at each iteration, we compare each element. The moment we encounter a nonidentical pair, we can return FALSE because our string can’t be a palindrome.

We will construct the solution step by step and the first step is to set up two pointers and move them toward the middle of the string. We can do that with the following code snippet:

def is_palindrome(s):
    print("String to check: ", s, ". Length of string: ", len(s), sep='')
    left = 0
    right = len(s) - 1
    i = 1
    while left < right: # The terminating condition for the loop is when both the pointers reach the same element or when they cross each other.
        print("In iteration ", i, ", left = ", left, ", right = ", right, sep="")
        print("The current element being pointed to by the left pointer is '",
              s[left], "'", sep="")
        print("The current element being pointed to by the right pointer is '",
              s[right], "'", sep="")
        left = left + 1  # Heading towards the right
        right = right - 1  # Heading towards the left
        i = i + 1
        print("-" * 100)
    print("Loop terminated with left = ", left, ", right = ", right, sep="")
    return ("The pointers have either reached the same index, or have crossed each other, hence we don't need to look further.")
# Driver code
def main():
    test_cases = ["RACECAR", "ABBA", "TART"]
    i = 1
    for s in test_cases:
        print("Test Case #", i)
        print(is_palindrome(s))
        print("-" * 100, end="\n\n")
        i = i + 1
if __name__ == '__main__':
    main()

Enter to Rename, Shift+Enter to Preview

Valid Palindrome

That's how we always traverse in opposite directions with the help of two pointers. The termination condition for our code is that the left pointer should always be less than the right pointer, because the moment they cross each other, we reach the middle of the string and don't need to go any further. We can check how this works with our example.

In the code sample above, we see that in the case of the palindromic strings, at each step in the traversal toward the middle of the string, the characters at both the left and the right indexes are identical. However, with the third test case, “TART” (which isn't a palindromic string), in the second iteration of the loop, we see that our output identifies that the characters at the left and right indexes aren't the same. This observation allows us to add a simple check to our code.

If we encounter a nonidentical pair, we can simply return FALSE, because the string isn't a palindrome, and we don't need to test any further. Otherwise, we're able to traverse to the middle of the string. In this case, we return TRUE, because each element has a match at the expected position in the string.

def is_palindrome(s):
    left = 0
    right = len(s) - 1
    print("The element being pointed by the left index is", s[left], sep = " ")
    print("The element being pointed by the right index is", s[right], sep = " ")
    while left < right:
        print("We check if the two elements are indeed the same, in this case...")
        if s[left] != s[right]:  # If the elements at index l and index r are not equal,
            print("The elements aren't the same, hence we return False")
            return False    # then the symmetry is broken, the string is not a palindrome
        print("They are the same, thus we move the two pointers toward the middle to continue the \nverification process.\n")
        left = left + 1  # Heading towards the right
        right = right - 1  # Heading towards the left
        print("The new element at the left pointer is", s[left], sep = " ")
        print("The new element at the right pointer is", s[right], sep = " ")
    # We reached the middle of the string without finding a mismatch, so it is a palindrome.
    return True
# Driver Code
def main():
    test_cases = ["RACEACAR", "A", "ABCDEFGFEDCBA",
                  "ABC", "ABCBA", "ABBA", "RACEACAR"]
    for i in range(len(test_cases)):
        print("Test Case #", i + 1)
        print("-" * 100)
        print("The input string is '", test_cases[i], "' and the length of the string is ", len(test_cases[i]), ".", sep='')
        print("\nIs it a palindrome?.....", is_palindrome(test_cases[i]))
        print("-" * 100)

Enter to Rename, Shift+Enter to Preview

Valid Palindrome

def is_palindrome(s):
    left = 0
    right = len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left = left + 1 
        right = right - 1
    return True
# Driver Code
def main():
    test_cases = ["RACEACAR", "A", "ABCDEFGFEDCBA",
                  "ABC", "ABCBA", "ABBA", "RACEACAR"]
    for i in range(len(test_cases)):
        print("Test Case #", i + 1)
        print("-" * 100)
        print("The input string is '", test_cases[i], "' and the length of the string is ", len(test_cases[i]), ".", sep='')
        print("Is it a palindrome?.....", is_palindrome(test_cases[i]))
        print("-" * 100)
if __name__ == '__main__':
    main()

Enter to Rename, Shift+Enter to Preview

Valid Palindrome

Solution summary#

Initialize two pointers and move them from opposite ends.
The first pointer starts at the beginning of the string and moves toward the middle, while the second pointer starts at the end and moves toward the middle.
Compare the elements at each position to detect a nonmatching pair.
If both pointers reach the middle of the string without encountering a nonmatching pair, the string is a palindrome.

Time complexity#

The time complexity is $O(n)$ , where $n$ is the number of characters in the string. However, our algorithm will only run $(n/2)$ times, since two pointers are traversing toward each other.

Space complexity#

The space complexity is $O(1)$ , since we use constant space to store two indexes.

Solution: Valid Palindrome

Statement#

Solution#

Naive approach#

Optimized approach using two pointers#

Step-by-step solution construction#

Just the code#

Solution summary#

Time complexity#

Space complexity#