Thread by @SimonHoiberg

🔥 Kill this interview question 🔥

🎯 The challenge
Write a function that — given a string — returns true if the string is a palindrome or false otherwise.

Let's look at 11 different approaches to solving this in JavaScript 👇🧵

👌 The definition

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as taco cat or madam or racecar or the number 10801.

- Wikipedia

According to the definition, we need to strip potential non-alphanumeric characters thus convert to lower-case.

So in all of the following solutions, we will be using a "clean" function to get a clean sequence of characters.

To measure the different approaches, I'm gonna run them all through palindromes of various lengths, and measure runtime performance in NodeJS.

- A small palindrome of 10 characters
- A medium palindrome of 1000 characters
- A large palindrome of 5000 characters

🔸 Using a for loop

For each character at position i, we compare with the character at position i from the end.
If any of these does not equal, we can reject the input as being a palindrome and break out of the loop and return false.

Performance:
Small: 0.0731 ms
Medium: 0.1267 ms
Large: 0.6272 ms

Pros:
Performs very well, even on large strings.
We are able to return as soon as we identify the first violation.

Cons:
In the world of ES6, this solution appears a bit “clumsy” to read.

🔸 Using for…of

Similar to a for loop.
With this approach, we convert the string into an array and then we iterate through each element.

For each element, we remove the last element of the array using pop(), and then we compare the current element with that.

Performance:
Small: 0.0415 ms
Medium: 0.0966 ms
Large: 0.9997 ms

Pros:
Performs good, and looks fairly readable.
We are able to return as soon as we identify the first violation.

Cons:
We imperatively mutate the array, which cost us a bit of performance.

🔸 Using split, reverse and join

Alright, let’s turn to use some of JavaScripts inbuilt methods.

This solution is very intuitive — we will simply reverse the string and compare it to the original. If they are equal, it’s a palindrome.

Performance:
Small: 0.1633 ms
Medium: 0.1986 ms
Large: 1.5192 ms

Pros:
Concise and very readable.
Easy to understand what is going on.

Cons:
Not the most well-performing, namely on small strings.

🔸 Using forEach

This solution is quite similar to solutions 1 and 2.
We are going to convert the string into an array and then apply forEach on it.
For each iteration, we are doing the same comparison as in solution 1, but this time we will flag a variable in the outer scope.

Performance:
Small: 0.0444 ms
Medium: 0.1487 ms
Large: 1.2537 ms

Pros:
Plus points for using ES6 methods.
Overall more readable and easy to understand.

Cons:
With forEach we cannot break the iteration, nor can we ensure only doing string.length / 2 total iterations.

🔸 Using map

We return a new array with true/false for each element, representing whether this character matches the same character from the end.

Finally, we are using some to check if the new array contains a false.
If it doesn’t the string is a palindrome, otherwise not.

Performance:
Small: 0.0644 ms
Medium: 0.1560 ms
Large: 0.9630 ms

Pros:
Plus points for using ES6 methods.

Cons:
With map we cannot break the iteration, nor can we ensure only doing string.length / 2 total iterations.

🔸 Using reduce

This solution is similar to using forEach, instead, we use reduce.

The key difference here is, that where we had to flag a variable in the outer scope using forEach, we can pass this flag into the next iteration using reduce.

Performance:
Small: 0.0425 ms
Medium: 0.1830 ms
Large: 0.8459 ms

Pros:
Plus points for using ES6 methods.

Cons:
If the check fails early, we keep passing on false to the next iteration.
This may seem like quite a waste, namely on larger strings.

🔸 Using every

We convert the string into an array, and then we apply every to it.

Performance:
Small: 0.0414 ms
Medium: 0.1977 ms
Large: 1.4204 ms

Pros:
Concise.
Will break early if a character does not match.

Cons:
We can’t ensure only doing string.length / 2 total iterations.
In the case of a palindrome, every will iterate through the whole array.

🔸 Using recursion

Let’s solve this problem by using recursion.
The idea is to compare the first and the last character of a string.
If they are equal, we are going to create a substring where the first and last letter is removed, and then recursively apply the function again.

Performance:
Small: 0.0842 ms
Medium: 5.1806 ms
Large: 108.5716 ms

Pros:
The interviewer may give you credit for knowing how to handle recursion.
Other than that, there is probably not much good to say about this solution.

Cons:
There are, on the other hand, some considerations here.
We are opening a lot of function closures, and building up a — potentially — large call stack.

Notice how the performance on the large string blows through the roof here, compared to any of the previous solutions.

Alright - let's take it to the next level now 🤩

Let’s imagine that the interviewer asks you if there is a way that we can approximate how “close” a given string is to be a palindrome.

Let's look at 3 approaches.
I will use these test-strings for verification 👇

🔸 Calculating the match percentage

Let's revisit the example above using map.
But we're gonna refactor it a little.

Let's count the number of 'false' and divide it with the total length to get a match percentage.

Result:
100.00%
80.95%
27.27%
0.00%
0.00%

Performance:
Small: 0.0718 ms
Medium: 0.2233 ms
Large: 1.4426 ms

🔸 Using cosine similarity

The idea is, that we are going to split the string into two equal parts and then revert one of them.

Then we convert them into their vector representation in n dimensions, n being the length of the half strings.

Then we are going to measure the angle between these vectors.
The bigger the angle, the bigger the mismatch between the strings.

Sounds fun, right? 🤩

Let's do this!! 👇

The tricky part is to represent a character as a number that includes both the character itself and its position in the string.

Here, I’m using the characters charCode and then subtracting the position in the array from that number.

Alright, assuming we've converted both strings into vector representations, we can now proceed with the following steps:

- Calculate the dot product of the two vectors
- Calculate the magnitude of each vector
- Calculate the cosine of the angle between the vectors

Since the cosine of the angle is in the range of [-1; 1], we want to convert this into a percentage, where -1 represents 0% and 1 represents 100%.

We simply add 1 to the cosine and divide it by to, and finally multiplies with 100.

Let's put it all together 👇

Result:
100.00%
90.04%
57.90%
69.17%
12.37%

Performance:
Small: 0.0314 ms
Medium: 0.2597 ms
Large: 1.5066 ms

🔸 Using Levenshtein distance

Are you still here after all that? 😅
Haha - you're insane!

Keep reading, cause it's getting worse 👇

Just as with the previous approach, we are going to start by splitting the string up into two half strings and revert the second one.

The idea is to calculate the Levenshtein distance between these two strings and convert that into a measure of percentage.

The Levenshtein distance is the minimum number of single-character edits required to change one word into the other.

We can calculate the Levenshtein distance using the following formula 👇

A single-character edit can be either an insertion, a substitution or a deletion.

For example, if we calculate the Levenshtein distance of the two words “HONDA” and “HYUNDAI”, we get 3:

1. Delete the letter "Y".
2. Substitute "O" with "U"
3. Insert "I"

Let’s go through this setup, and see how we can use this to approximate a string in terms of a palindrome.

- Split the string into two even half strings
- Reverse the second half
- Create a matrix
- Fill the matrix
- Count edits
- Convert into percentage

Let's put the whole thing together, and we get something like this 👇

Result:
100.00%
80.00%
27.27%
6.67%
0.00%

Performance:
Small: 0.0635 ms
Medium: 32.5343 ms
Large: 616.9648 ms

Are you kidding me?!
Did you really read all the way to here?

You are either extremely committed or totally crazy 😅

Anyway! These are all approaches to determine (or approximate) whether a string is a palindrome.

It's a common interview question, and you're gonna score great points if you can ace this by arguing for different approaches and their pros and cons ✌️