Algorithms 101: How to check if a string is a palindrome
Tags: algorithms, tutorial, beginners, programming
Published: 2023-02-14 16:28:22

When it comes to job search and coding interviews, you will need to be able to think through [**algorithm-based interview problems**](https://www.educative.io/blog/ace-top-15-java-algorithm-questions?eid=5082902844932096) in front of an interviewer or panel. Practicing at the very start will put you on the path to success in technical interviews. 

A common question you can expect to implement is **checking if a string is a palindrome**. To get you familiar with this problem, we will review what an algorithm is and learn how to solve this problem in several ways.

**In this article, we will look at:**
* [Algorithms refresher](#algorithms)
* [Coding challenge breakdown](#breakdown)
* [Solution 1: Compare a string with its reversed version](#1)
* [Solution 2: Iterate using for loop](#2)
* [Solution 3: Use Recursion](#3)
* [What to learn next](#next)

<a name="algorithms"></a>

## Algorithms refresher

Generally speaking, an algorithm is a **set of steps** it takes to do something. Think about what it takes to bake a cake or change the oil in your car. All of the steps and all of the tools or ingredients needed to make those things happen in order is a part of an algorithm. 

> At a high level, an algorithm is a **recipe** or guide on how to execute a series of steps that will solve a problem. 

In computer science, algorithms refer to a **sequence of well-defined instructions** that tell the computer what to do to solve a problem. Just like we have to have a series of steps to bake a cake, we need a series of well-defined instructions to create an algorithm that will solve our problem.

There are all kinds of algorithms out there, and they commonly come up in coding interviews. Algorithms are **applied to different data structures**. So, we take a data structure and apply an algorithm to do certain operations on it. 

In this article, we will look at how to manipulate a string with an algorithm, specifically, how to check if a string is a palindrome. 

<br>

<a name="breakdown"></a>

## Coding challenge breakdown

The goal of this algorithm is to input a string and use a function to check if it is a palindrome.

A palindrome is a word or phrase that reads the same backward and forward. When palindromes are the length of a sentence, they ignore capitalization, punctuation, and word boundaries. 

> **For example:** racecar, 1001, 11/11/11, or 11:11.

![Palidrome](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lg8s034eqyt7nhouk3vy.png)

### Prompt

Given a value, write a function that will test to see if the string is a palindrome or not. Return `true` if it is or `false` if it’s not. 

<br>

### Examples: 

```html
isPalindrome(“”) // true
isPalindrome(1010) // false
isPalindrome(“taco Cat”) // true
isPalindrome(“Was it a car or a cat I saw?”) // true
isPalindrome(“hello”) // false
isPalindrome(“momma made me eat my m&ms”) //false
```

<br>

### Approach

There are several different approaches to take with this problem that we will go through below. But first, let’s talk it through as if we were just explaining the answer to someone without code. 

*So, we are given a value. What is that value? Is it a string? Is it something else?* 

The prompt doesn't indicate what the type of the value was. If you were in an interview situation, this could be a place where you would **confirm with the interviewer** if the given value was a string. 

Since a palindrome could technically be anything, let’s take care of all types and take a look at all edge cases. In most cases, in a technical interview, you will not need to worry about the extreme edge cases, but an interviewer will notice if you speak up about it. 

Write a function that will test whether or not that value is a palindrome. This should indicate that they want a boolean value (`True` or `False`).

**Things we know so far:**
* Our value can be a string, number, or object 
* We need to return a boolean value
* A palindrome ignores case, spaces, and punctuation

<br>

### Pseudocode

First, we need to consider the type of value. 
* If it is a **number**, we need to change it to a string to compare how it reads backward and forward. 
* If it is an **object**, we need to somehow also change it to a string to do a comparison. 
* If it is a **string**, we can forge ahead. 
* If we have **null or undefined**, how do we handle that? 

Once we have figured out the type and changed it to a string, we need to prep the string so we can read it left-to-right and right-to-left without any non-alphanumeric characters.

We need to take care to remove all the extraneous stuff. We can do this in several ways, for example, by iterating through the string to remove certain characters.

We also need to take care to ignore whether or not letters or uppercase or lowercase. We can do that by either making everything capitalized or everything lowercase. 

> Once all non-alphanumeric characters are gone, and we have our strings in one case, now our string is **ready to test**!

Think about the possible ways to handle this problem: 
* Compare a string with its reversed version (JS Methods)
* Iterate using for loop and check to see if a character on another side of the string `===`
* Use [recursion](https://www.educative.io/blog/recursion) to check the first and last letters before invoking the function again with the shortened string 

<br>

### JavaScript code setup

There are several different ways to solve this problem. As long as you can explain your approach and you arrive at the correct answer, your approach is probably just fine. These are just three of the possible ways you can figure out whether or not a value passed is a palindrome or not. 

No matter your approach, the setup requires that we ready the value to be tested. Let’s go ahead and do that now. This will be the same for all three solutions.

```javascript
const stripNonAlphaNum = (val) => {
 let str;
 switch(typeof val) {
   case "number":
     str = val.toString();
     break;
   case "object":
     str = JSON.stringify(val);
     break;
   case "string":
     str = val;
     break;
   case "boolean":
     str = null;
     break;
 }
 if(str === null || str === undefined) {
   return null;
 }
 else if(str.length === 0){
   return "";
 }
 else {
   let newStr = str.toLowerCase().replace(/[\W_ ]/g, "");
     return newStr;
 }
 }
```

In this code we use the `typeof` on our `val` to create a switch statement that will assign the variable `str` to a string version of the value. If the `val` is a number, we just need to make it a string. 

If it’s an object, you can stringify it by using the JSON method of the same name. If it’s a boolean, set the string to null as booleans are not palindromes

The next lines of code test to see if the string length is `0` or if the `str` is undefined or null. If an empty string, we want to assign the `str` to an empty string. Otherwise, we are going to return null. 

> **Note:** Technically an empty string is a palindrome as it reads the same backward and forward.

Finally, we use a couple of JavaScript methods to make everything lowercase and to replace a search term with an empty string. This search term is a regular expression that looks for all non-alphanumeric characters, underscores, and spaces in a string. 

We assign this expression to a variable called `newStr` and return it.   

<br>

<a name="1"></a>

## Solution 1: Compare a string with its reversed version

We are going to use the split, reverse, and join methods to test to see if the reversed version of the string is the same as the string itself. 

```javascript
const isPalindrome = (val) => {
 let str = stripNonAlphaNum(val);
 if(str === null) return false;
 return str.split('').reverse().join('') === str;
}
```

In the first line of the function, we assign `str` to the what is returned from the `stripNonAlphaNum()` function that uses regex to take away all of the extraneous characters we don’t need and to lowercase all of the characters. 

Here is a set of tests that you can use to make sure your code works properly: 

```javascript
console.log(isPalindrome("taco Cat")); // true
console.log(isPalindrome(1010)); // false
console.log(isPalindrome("Was it a car or a cat I saw?")); // true
console.log(isPalindrome({a: "b", b: "a"})); // true
console.log(isPalindrome(null)); // false
console.log(isPalindrome(false)); // false
console.log(isPalindrome("")); //true
```

<br>

<a name="2"></a>

## Solution 2: Iterate using for loop 

In this solution, we are going to use a regular for loop to iterate through the string. On each iteration, let’s take a look at the corresponding letter that’s the same distance from the end to see if they are equal. 

If we get to the center of the word and everything is equal, we have a palindrome. Else, we return `false`. 

```javascript
const isPalindrome =(val) => {
 let str = stripNonAlphaNum(val);
 if(str === null) return false;
 for(let i = 0; i < str.length/2; i++) {
   if(str[i] !== str[str.length - 1 - i]) {
     return false;
   }
 }
 return true;
}
```

Here, we only iterate to the midpoint of the string because we are checking the other half of the string to its counterpart in the front half of the string. 

A good approach when it comes to solving problems is to always **check for false values**. If we come to a pair of letters that don’t match, we know it’s not a palindrome and we can stop there. This is what the first line in the for loop is doing. 

We are checking to see if the current character is equal to the character at the same spot from the end. If it doesn’t match, return `false`. 

If we get through the whole for loop and the conditional inside the for loop hasn’t been triggered, that means all the characters are the same and we have a palindrome. 

<br>

<a name="3"></a>

## Solution 3: Use Recursion

In this third and final solution, we are going to use recursion to find out if our value is a palindrome or not. Remember with recursion, we need to have a base case else we will exceed our maximum call stack size. 

```javascript
const isPalindrome = (val) => {
 let str = stripNonAlphaNum(val);
 if(str == null || str === undefined) return false;
 
 let length = str.length;
 if (length === 0 || length === 1) {
   return true;
 }
 if (str[0] === str[length - 1]) {
   return isPalindrome(str.slice(1, length - 1) );
 } 
 return false;
};
```

We start with getting our string value by invoking the function we wrote to lowercase characters and get rid of all the non-alphanumeric characters. If it passes the null test, we will check the string against our base case. 

> If the base case passes, it means we have checked all of our characters, and we have a palindrome. 

The next conditional is where our recursion happens. We want to compare the first letter of the string to the last letter of the string. 

If they are equal, we’ll return the `isPalindrome()` function, and pass in a copy of the string minus the first character and the last character as our argument. 

The recursion will continue to happen as long as we have matching letters or until we hit our base case. If we hit our base case, our `str` is a palindrome, and we return `true`. If at any point we have characters that don’t match, we return `false`. 

<br>

<a name="next"></a>

## What to learn next

Algorithms can be challenging. The more you practice, the better you will get at identifying patterns that will help you create a process for solving the problem. 

As long as you understand the problem, you should be able to get to a solution with time.  A first-pass solution is still a solution. It may not be the best solution, but you can always refactor to make it better.

There are still more algorithms to study to prepare for coding interviews. **Your next steps are:**
* Print duplicate characters from a string
* How to reverse a string
* How to find duplicate characters in a string
* [Graph algorithms](https://www.educative.io/blog/data-structures-101-graphs-javascript?eid=5082902844932096)

Educative's learning path **[Ace the JavaScript Coding Interview](https://www.educative.io/path/ace-javascript-coding-interview?eid=5082902844932096)** offers hands on practice with all of these problems and more. It's your one-stop-shop for prepping for coding interviews. 

You’ll cover everything from Data Structures to System Design, and by the time you’re done, your skills will be polished enough to impress at any company.

*Happy learning!*

### Continue reading about algorithms on Educative
* [Algorithms 101: how to use Merge Sort and Quicksort in JavaScript](https://www.educative.io/blog/algorithms-101-merge-sort-quicksort?eid=5082902844932096)
* [JavaScript Array Methods: how to use map and reduce](https://www.educative.io/blog/javascript-array-methods-map-reduce?eid=5082902844932096)
* [7 JavaScript data structures you must know](https://www.educative.io/blog/javascript-data-structures?eid=5082902844932096)

### Start a discussion 
What is your favorite coding algorithm? Was this article helpful? Let us know in the comments below!