Solution: Valid Palindrome

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≤1 \leq s.length ≤2×105\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.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.