How to Validate a Palindrome

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:

let str = 'thisisnotapalindrome';
isPalindrome(str);
// false

str = 'racecar';
isPalindrome(str);
// true

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

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

---

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.

Solution: True

---

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:

function isPalindrome(str) {
    // Calling reverse function
    const reversed = str.split('').reverse().join('');

    // Checking if both strings are equal or not
    if (str == reversed) {
        return true;
    }
    return false;
}

console.log(isPalindrome('racecar'));

Order

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

• 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

Solution:

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

---

Multiple Choice

What will the following pseudocode do to an input string?

def reverse_str(str):
  start = 0
  end = len(str)-1
  str_copy = [letter for letter in str]
  while start < end:
    temp = str_copy[start]
    str_copy[start] = str_copy[end]
    str_copy[end] = temp
    start += 1
    end -= 1
  return "".join(str_copy)

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

Solution: Reverse the string

---

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?

function isPalindrome(str) {
    let left = 0;
    let right = str.length - 1;
    let leftChar;
    let rightChar;

    while (left < right) {
        leftChar = str.charAt(left);
        rightChar = str.charAt(right);

        if (leftChar == rightChar) {
            left++;
            right--;
        } else {
            return false;
        }
    }

    return true;
}

console.log(isPalindrome('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:

racecar
^     ^
racecar
 ^   ^
racecar
  ^ ^
racecar
   ^
True

Multiple Choice

What is the run time of the following code?

def reverse_str(str):
  start = 0
  end = len(str)-1
  str_copy = [letter for letter in str]
  while start < end:
    temp = str_copy[start]
    str_copy[start] = str_copy[end]
    str_copy[end] = temp
    start += 1
    end -= 1
  return "".join(str_copy)

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

Solution: O(n)

---

Final Solution

function isPalindrome(str) {
  if (!str || str === "") {
    return true;
  } else {
    let left = 0;
    let right = str.length - 1;
    let leftChar;
    let rightChar;

    while (left < right) {
      leftChar = str.charAt(left).toLowerCase();
      rightChar = str.charAt(right).toLowerCase();

      if (isAlphaNumeric(leftChar) && isAlphaNumeric(rightChar)) {
        if (leftChar == rightChar) {
          left++;
          right--;
        } else {
          return false;
        }
      } else {
        if (!isAlphaNumeric(leftChar)) {
          left++;
        }
        if (!isAlphaNumeric(rightChar)) {
          right--;
        }
      }
    }

    return true;
  }
}

function isAlphaNumeric(c) {
  if (/[^a-zA-Z0-9]/.test(c)) {
    return false;
  } else {
    return true;
  }
}

console.log(isPalindrome("A Santa Lived As a Devil At NASA"));

Check out more visual tutorials for technical challenges at AlgoDaily.com and try out our daily coding problem newsletter!

Comments

[Aleksandar Panic]

Here is a bit of a shorter and optimized version of it.

Also few more things:

• There is no need to go from 0 to string.length - 1. You only need to go to a half of the string because you are checking from the both sides, they will meet in half.
• Also alphanumeric check is a bit too much to do per character since you can just transform the whole string into data you want to to use beforehand.
• There is no need for left / right variables because you can always calculate them as left = string[currentIndex] and right = string[lastIndex - currentIndex]

function isPalindrome(str) {
    str = str ? str.toLowerCase().replace(/[^a-zA-Z0-9]/g, '') : "";
    const maxHalf = str.length / 2;
    const lastIndex = str.length - 1;

    for (let currentIndex = 0; currentIndex < maxHalf; currentIndex++) {
        if (str[currentIndex] !== str[lastIndex - currentIndex]) {
            return false;
        }
    }

    return true;
}

Also some line explanations:

• Line str = str ? str.toLowerCase().replace(/[^a-zA-Z0-9]/g, '') : ""; does some validation checks and handles lowercase and non-alphanumeric characters.
• Lines const maxHalf = str.length / 2; and const lastIndex = str.length - 1; are mostly for optimization so that the for doesn't calculate them again during each iteration

[Jon Randy 🎖️]

I will never understand why people write functions that are basically:

function testSomething(param) {
   if (someBooleanExpression) {
      return true;
   } else {
      return false;
   }
}

If I saw this from a job applicant in a coding test, I would likely not hire them - unless they could give a convincing reason why they've done it this way.