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) {

}

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;
}

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

" racecar "
  ^     ^
 left  right

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) {

  }
}

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--;
  }
}

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;
}

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. 😄