DEV Community

Cover image for How to Determine if a String is a Palindrome (in JavaScript)
Sean Welsh Brown
Sean Welsh Brown

Posted on

How to Determine if a String is a Palindrome (in JavaScript)

When it comes to solving problems in an interview setting as a software engineer, few topics come up quite as often as string manipulation. And when it comes to string manipulation, few specific concepts come up as frequently as Palindromes.

What is a Palindrome?

For those who might not know, a Palindrome according to the wikipedia page on the subject is defined as:

...a word, number, phrase, or other sequence of characters which reads the same backward as forward.

Some examples of palindromes in real words are:

  1. racecar
  2. madam
  3. kayak
  4. noon

Though in the context of programming, a palindrome need not even be a real word (or even made up of letters.) Some examples of this type might be:

  1. asdfgfdsa
  2. wrcmmcrw
  3. 54645
  4. !020!

And so on.

Why does this come up in technical interviews?

As you'll see when we write our code, palindromes are a very fundamental algorithmic practice topic because they involve multiple concepts that engineers use regularly on the job, such as:

  1. Being able to traverse through and/or manipulate a string.
  2. Knowing how to set multiple pointers and use/move them within a repeating loop.
  3. Understanding how to take something that's simple for a human being to do (see if a word is a palindrome) and explain that to a computer in a set of repeatable instructions.

That last one in particular is a core fundamental of problem solving in computer science. Oftentimes the easiest things for us to do as humans are the hardest things to represent simply and efficiently in code.

How do we implement it in code?

I'm glad you asked!

In the example we'll be going over here, we're going to implement a simple algorithm that will detect if a given string is (or is not) a palindrome. While this may seem like a simple task, understanding it well can give you an advantage when harder palindromic questions are asked in interviews, or when they come up in your own practice.

Think of this solution as more of a building block, or a tool that you'll have in your toolbox to use on more difficult questions, rather than the end of all discussions on palindromes in code.

Let's get down to it!

Step 1: Understand how to solve the problem

Before we code, we should first think through how we might solve this.

When we look at a word or a series of characters as humans, we recognize something as a palindrome by reading through the word up until we hit the "middle" of the word, then see that the second half of the word contains the same letters or characters as the first half.

Think of it like climbing a hill up to the top, and then noticing that the other side of the hill looks exactly the same on the way down.

Trying to do it this way in an algorithm might work if we kept track of the letters we've seen as we step through the string, but we'll realize quickly that there isn't as simple a way to tell the computer what the "middle" of the string is, conceptually, and we'll also need to use extra space to store the first part of the string that we saved on the way there.

An easier way is to think back to that "hill" analogy I mentioned; if both sides of the string are the same on the way up and down, then couldn't we start at both the beginning and the end of the string and work our way to the middle at the same time?

Yes we could! And that's precisely what we'll do in our code.

Step 2: Code it!

Let's start by declaring our function, giving it a name and a parameter for a string to be passed in as an argument:

function isPalindrome(string) {

}
Enter fullscreen mode Exit fullscreen mode

Now, let's create two pointers that we'll use to traverse the string. One will start at the beginning of the string, and the other will start at the end.

We'll name these left and right, but they could be anything you'd like:

function isPalindrome(string) {
  let left = 0;
  let right = string.length - 1;
}
Enter fullscreen mode Exit fullscreen mode

In an example string, these two pointers would start in the following locations:

" racecar "
  ^     ^
 left  right
Enter fullscreen mode Exit fullscreen mode

Now, let's write the loop that we'll do all of our logic inside of. We'll use a while loop here, since we want the loop to continue perpetually until its end-case is met, when we reach the "middle" of the string:

function isPalindrome(string) {
  let left = 0;
  let right = string.length - 1;

  while (left <= right) {

  }
}
Enter fullscreen mode Exit fullscreen mode

This works because we know that if left ever becomes greater than right, that means we've passed the middle of the string and we shouldn't be continuing our loop.

Now we'll implement our core bit of logic, and the incrementing/decrementing of our pointers to traverse the string:

function isPalindrome(string) {
  let left = 0;
  let right = string.length - 1;

  while (left <= right) {
    if (string[left] !== string[right]) return false;
    left++;
    right--;
  }
}
Enter fullscreen mode Exit fullscreen mode

What we're doing here is using a comparison operator to check if the character on the left does not match the character on the right. If this is the case, we know that the string can't be a palindrome, and we immediately return false as our function's output.

If the characters do match, we know we should continue to traverse the string, and we increment the left pointer and decrement the right pointer respectively.

Now, all that's left to do is put in our other return value, if the string is a palindrome:

function isPalindrome(string) {
  let left = 0;
  let right = string.length - 1;

  while (left <= right) {
    if (string[left] !== string[right]) return false;
    left++;
    right--;
  }

return true;
}
Enter fullscreen mode Exit fullscreen mode

The true return value is outside of the while loop, because if we complete the loop without ever returning a false value, that means we've confirmed the string to be a palindrome.

And we're done, woohoo!


If you've read this far, I hope this little tutorial helped in understanding this fundamental bit of algorithmic logic.

While this solution may be very simple, it's important to keep in mind for more complex problems and algorithms where you may need to expand on it, or use it nested further within a greater problem. I can guarantee you that it will show up in your studies or assessments at some point, in some form!

Thanks so much for reading, and happy coding. πŸ˜„

Top comments (11)

Collapse
 
mberger75 profile image
Marc Berger • Edited

Thanks for sharing, i don't understand why you made it so complicated?

Just convert the string into an array with split, reverse the returned array, convert it into a string with join and compare it with the original string.

const isPalindrome = str => str.split('').reverse().join('') === str;
Enter fullscreen mode Exit fullscreen mode
Collapse
 
wannabehexagon profile image
ItsThatHexagonGuy • Edited

I think the author's main goal is to show the reader how to check if a string is a palindrome algorithmically, using javascript methods is fine but it makes the code idiomatic/would make most sense for a js dev.

Also, generally performance should never be a primary factor. Writing clean, easy to understand and maintainable code is the goal any dev should have. Because your example is idiomatic to js devs in a js codebase it will seem more intuitive to any new dev as opposed to the author's.

I saw a few comments talking about perf. Performance shouldn't be a decision factor. Performance can be optimized if it becomes a problem.

Collapse
 
seanwelshbrown profile image
Sean Welsh Brown • Edited

Yes, this was originally my goal. I love this that sparked so much discussion on different ways of approaching the same problem!

I mainly approached this (relatively simple problem) from the perspective of how someone might solve it in a more language agnostic, algorithmic way that touched on a few other aspects of problem solving that new developers might not have as much practice with, like moving pointers and checking/comparing string characters similar to how you might compare array elements.

I was aiming for more of an informational approach than the simplest solution, but I appreciate that there are comments on here now for folks to see other solutions that work as well (especially using in-built JS methods, since that's a perfectly valid approach too.) πŸ˜ƒ

Collapse
 
apmccartney profile image
Austin McCartney

generally performance should never be a primary factor

The combination of generally and never seems confused... and the sentiment is troubling...

Especially when developing software libraries,

  1. you aren't positioned to understand whether performance compromises are problematic, and
  2. the client isn't in positioned to resolve those problems

Empathy should be out guiding principle, both for those inheriting and maintaining the code we write and for those consuming it.

Thread Thread
 
wannabehexagon profile image
ItsThatHexagonGuy • Edited

"generally" => most cases so you can read it out as "in most cases, performance should never", which means performance should only be a deciding factor in specific situations where the operation is costly in some way, is used frequently, etc.

For example, the palindrome code from the post doesn't have to be optimized for performance but say you were batching a bunch of expensive asynchronous tasks, you could use Promise.all and generators together to do so. The question you should ask before working on this optimization is whether or not maintaining that extra complexity is going to bring any net benefit. For the palindrome example, there's little to no net benefit so going with an idiomatic approach is fine, even if it's slower.

I don't understand why you think that a library author is in no position to determine whether or not a performance compromise is problematic. Making decisions like that is literally the job of a developer. True, consumer's are in no position to resolve such problems, and that's exactly why building healthy communities is important, so consumers come back to you and tell you that something isn't doing the job well (when it comes to libraries, for product consumers, you can use analytics, performance metrics, etc.)

Yes, Empathy should be every developer's guiding principle, and unnecessary performance optimizations have nothing to do with being empathetic. I'm not saying optimizations are unnecessary but optimizing unnecessarily, is unnecessary.

Collapse
 
trongtai37 profile image
trongtai37

Hi, i think your code look shorter and cleaner but the fact that author's code run faster with less complexity!.

Collapse
 
gustavosfq profile image
Gustavo Flores
function isPalindrome(string) {
  let left = 0;
  let right = string.length - 1;

  while (left <= right) {
    if (string[left] !== string[right]) return false;
    left++;
    right--;
  }

    return true;    
}

const isPalindrome2 = str => str.split('').reverse().join('') === str;

console.time('isPalindrome');
for(var i = 0; i < 100000000; i++) {
    isPalindrome('asdfgfdsa')
}
console.timeEnd('isPalindrome')
console.time('isPalindrome2');
for(var i = 0; i < 100000000; i++) {
    isPalindrome2('asdfgfdsa')
}
console.timeEnd('isPalindrome2')    
isPalindrome: 4212.408935546875 ms
isPalindrome2: 60999.298095703125 ms
Enter fullscreen mode Exit fullscreen mode
Thread Thread
 
amplanetwork profile image
Ampla Network • Edited

Not so sure either we can do shorter and faster :-)

function isPalindrome(string) {
  let left = 0;
  let right = string.length - 1;

  while (left <= right) {
    if (string[left] !== string[right]) return false;
    left++;
    right--;
  }

    return true;    
}

const isPalindrome2 =(str) => {
  const l = str.length;
  for(let i=0; i< (l / 2) >> 0; i++) {
    if (str[i] !== str[l-i-1]) return false;
  }
  return true;
}

console.time('isPalindrome');
for(var i = 0; i < 100000000; i++) {
    isPalindrome('asdfgfdsa')
}
console.timeEnd('isPalindrome')
console.time('isPalindrome2');
for(var i = 0; i < 100000000; i++) {
    isPalindrome2('asdfgfdsa')
}
console.timeEnd('isPalindrome2')    ;

VM254:26 isPalindrome: 3210.27978515625 ms
VM254:31 isPalindrome2: 2888.925048828125 ms
Enter fullscreen mode Exit fullscreen mode
Collapse
 
cyberhck profile image
Nishchal Gautam

Less complexity? About performance, you can scale out, you need to write code which is easy to maintain, read and modify, when you look at original method, you won't know what's going on without some serious effort, with second one, within 2-5 seconds you understand exactly what it's doing

Collapse
 
bretgeek profile image
bretgeek • Edited

Don't get me wrong I like your algorithmic way better (it's probably faster too) but I have been on a kick lately trying to make things smaller. In case this is useful for anyone here is what I came up with in 6 lines. (probably better ways to do it too... bit shifting?)

function isPalindrome(str){
let strArr = str.split('');
let rev = strArr.reverse();
let str2 = rev.join('');
return str === str2;
}
Enter fullscreen mode Exit fullscreen mode

Use like:

let p = isPalindrome('racecar');
console.log(p);
Enter fullscreen mode Exit fullscreen mode
Collapse
 
jonrandy profile image
Jon Randy πŸŽ–οΈ
const isPalindrome = s=>[...s].reverse().join('')==s
Enter fullscreen mode Exit fullscreen mode