Palindrome problem

We will apply the abovementioned concepts on writing a simple algorithm for strings.

I came across this nice little challenge on Hackerrank. If you don’t know Hackerrank, have a look, it’s a great place to practice your algorithm writing skills.

Problem statement

The problem is very simple: Write a function that determines whether a string is a palindrome or not. The function should print YES if the word is a palindrome and NO if it’s not.

We call a word palindrome if it reads the same backwards as forwards. For example, the word string is not a palindrome because if we reverse it, we will get gnirts. But madam is, as it read the same backwards.

Note that the “word” doesn’t have to make sense, so it’s not necessarily a valid English word. We need to check if a given string is palindromic or not. In this sense we consider abcba a valid palindrome.

Breaking down the problem

Palindromic strings are symmetrical. Imagine that you draw a vertical line through the middle of the string. This way you’ll get two sides, both being the mirror image of the other side.

What this means for us is that we must get the same characters at equal distance from this “line of symmetry” if the string is a palindrome.

We need to compare pairs of characters. If the first and the last character of the string are different, the string cannot be palindromic and we are done. It’s not necessary to check further. If they are, we move on and compare the second and the second last characters. Again, in case of not matching characters, the investigation has finished as the string is not a palindrome. If they are the same too, we move on to the third and third last characters and so on.

If we systematically follow this method, we only need to go up to the imaginary line of symmetry, since the characters we compare will “meet” in the middle.

But strings can be of both even and odd lengths. For a string like abcba, the c in the middle doesn’t have a pair.

Although this doesn’t influence if the string is a palindrome, we need to be a little more careful when drawing the imaginary line of symmetry.

Building blocks in JS

Let’s start with the line of symmetry. It’s drawn through the middle of the string, so we need to find the length of the string first, and then divide it by 2. In case the string is of odd length, we need to round this number down. Again, the character in the middle won’t influence if the string is palindrome or not, so we can leave out the exact middle character. We can use the Math.floor method here, which rounds a given number down to the nearest integer.

In the next step we have to iterate over the characters up to the “line”, i.e. the half of the length of the string. A for loop can come handy when comparing the pairs of characters. If they are not the same, we immediately return NO, if they are, we keep iterating.

If everything goes well, we will eventually return YES.

Now all we need to know what to compare. String object in JavaScript has a method called charCodeAt. The method accepts the index of the character in a given string as an argument and returns an integer representing the code of the character in the Unicode character set. Each character has a code value based on which characters are recognized. For example, the characters of the English alphabet start at 97 (this is the a) and finish at 122 (z). Capital letters have different codes, and special characters, Greek or Cyrillic letters also have their codes.

By using charCodeAt we can make sure that the characters are the same only when the share the same character code.

Edge cases

It might be worth returning a gentle warning message when the function receives an empty string or a type other than string as input.

We can also consider a one-character string a palindrome as it “reads” the same both ways.

Solution

Our function will be called isPalindrome, as this name refers to the returned value and the purpose of the function. The function will have one argument called str, which is the sequence of characters we want to systematically check.

Let’s handle the edge cases first:

function isPalindrome(str) {
  if (!str || typeof str !== 'string') return 'Please enter a valid string!';
}

The '' is falsy, so we can simply write !str, which becomes truthy, so the condition kicks in and the statement (returing the string) gets evaluated. As a side benefit we also exclude all other falsy values this way.

If the value is truthy but it’s not a string type, we can also return the same message. You could separate the two cases and return custom messages for each but this will do it for us today.

With the step above, we only let valid, non-empty strings go to the checking phase and it’s certain that str now has a length, so an unexpected error won’t break the code.

I decided to save the length to a variable called length, because I will use it multiple times later and I think the code will become more readable this way. We can also calculate the exact position of the imaginary line of symmetry and store it in the halfLength variable:

const length = str.length;
const halfLength = Math.floor(length / 2);

Now we can work on the iteration. We only iterate up to halfLength and compare the mirror characters on either side inside the loop:

for (let i = 0; i < halfLength; i++) {
  if (str.charCodeAt(i) !== str.charCodeAt(length - 1 - i)) return 'NO';
}

Let’s see how the algorithm works with the string abcba.

The value of i is initially 0, so we check the code value of the first character, i.e. a (97). Next, we get the code of the last character. The length of the string is 5, so the index of the last character will be 4, i.e. length - 1. By subtracting the value of i from length - 1 ensures that we always compare mirror characters, in this case characters at index 0 and index 4 (since i is initially 0).

If the compared character codes are not equal, we will return NO and we are done. If the code values are matching (and they are in our case), we move on to the next pair, where i equals 1. Now the function compares the character at index 1 (b) and the second last character (length - 1 - i is 5 - 1 - 1 = 3), and turns out that both characters are the same again.

In the next step i is 2 but because of the condition of the for loop (i < halfLength, so i must be less than 2) is not met, so the iteration stops. We have the very middle character left (c), but again, it doesn’t play any role in the string being a palindrome.

All we have to do now is return YES, so the full code looks like this:

function isPalindrome(str) {
  if (!str || typeof str !== 'string') return 'Please enter a valid string!';

  const length = str.length;
  const halfLength = Math.floor(length / 2);

  for (let i = 0; i < halfLength; i++) {
    if (str.charCodeAt(i) !== str.charCodeAt(length - 1 - i)) return 'NO';
  }

  return 'YES';
}

Conclusion

Sitting back and thinking about the problem first is almost always beneficial when one needs to create an algorithm. In this nice little problem one might have had the idea of iterating over the whole string but as we have seen it we stop at the middle by abstracting away from the problem and simply visualizing the situation.

I hope you liked this article and until next time, enjoy coding!