Valid Palindrome in JavaScript: Two Pointers and Normalisation

Considered one of the 'LeetCode' type interview questions, the Valid Palindrome Problem is fairly straightforward:

“

Given a string, determine if it is a valid palindrome or not, considering only alphanumeric characters and ignoring case.

What is a Palindrome

Starting very simply, a palindrome is a word, phrase, number, or other sequence of characters that reads the same forwards as it does backwards. In doing this, we ignore spaces, punctuation, and capitalization.

For example, "level," "radar," and "A man, a plan, a canal, Panama!" are all valid palindromes.

Approach

The simplest way to solve this problem is to use a two‑pointer approach. We start with two pointers, one at the beginning of the string and the other at the end. As we move towards the centre of the string, we compare characters at both pointers to see if they are the same.

If they match, we continue; if they don't match then we know that the string is not a palindrome. As I mentioned: we ignore non‑alphanumeric characters and punctuation whilst comparing the characters.

Implementation

Implementation is relatively straightforward: we create a function which accepts a string, and then loop over each set of pointers in turn:

function isValidPalindrome(s: string): boolean {  // Convert the string to lowercase and remove non-alphanumeric characters  const cleanString = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();  // Initialise two pointers  let left = 0;  let right = cleanString.length - 1;  // Check if the characters at both pointers match  while (left < right) {    if (cleanString[left] !== cleanString[right]) {      return false;    }    left++;    right--;  }  return true;}

Testing the Function

If you want to really impress your interviewers, then adding some test coverage to your function using Jest will be sure to do so, whilst also making sure that the function works correctly. This can be done very easily using examples that we already know are valid palindromes or not:

import { isValidPalindrome } from './palindrome';describe('Valid Palindrome', () => {  it('should return true for valid palindromes', () => {    expect(isValidPalindrome('level')).toBe(true);    expect(isValidPalindrome('A man, a plan, a canal, Panama!')).toBe(true);    expect(isValidPalindrome('Able was I, ere I saw Elba!')).toBe(true);  });  it('should return false for non-palindromes', () => {    expect(isValidPalindrome('hello')).toBe(false);    expect(isValidPalindrome('algorithm')).toBe(false);    expect(isValidPalindrome('A palindrome is not always a palindrome!')).toBe(      false    );  });});

An Alternative Solution: Number‑Based Palindromes

Up until this point, I've only been focusing on strings of mixed alphanumeric characters. There is another version of this problem that focuses only on numeric inputs. For example: 1001 is a valid palindrome, whilst 1002 is not.

This gives us the opportunity to explore an alternative way of solving this problem using modern ES6 array methods:

const isNumberPalindrome = (num: number): boolean => {  const numStr = num.toString();  const reversedNumStr = numStr.split('').reverse().join('');  return numStr === reversedNumStr;};

Here, we:

1. Use num.toString() to convert the input number num to a string. This allows us to manipulate individual digits more easily.
2. We split the string (numStr) into an array of characters, reverse the array, and then use join to turn it back into a string. This gives us the reversed version of the original number, as a string.
3. Finally, we do a simple comparison between numString and reversedNumStr, and return the result. If they are equal, then the input was a valid palindrome and the function returns true.

Generally, this is a more efficient approach to the problem if we only need to handle numerics: it does away with the additional character manipulation we had to use above. However, it also doesn't use the two‑pointer method, and won't work as effectively with non‑numeric inputs.

The Wrap‑Up

The two‑pointer approach is a very common and incredibly useful coding pattern, and the Valid Palindrome Problem is (from my experience) an increasingly common interview question. Suffice it to say: I was offered the job!