JavaScript by Example: Palindrome Permutations (functional)

#javascript #programming #tutorial #beginners

"Javascript by Example" is a series of posts in which we are going to implement common coding interview & LeetCode-style problems and general utils - preferably in a minimal and elegant (but still learning-friendly) way, and compare different implementations.

Unlike classical palindrome (checking only if the string reads the same way from the left to right as from the right to left), this exercise is about finding out whether any permutation of the string is a palindrome.

For example, our function should return true for the string "racecar" because the word is a palindrome. But it should also return true for the string "aab" because it has a permutation "aba" (which is a palindrome).

Let's see first if we can implement this as a short, (relatively) functional one-liner.

Understanding the problem

If we think about palindromes for a moment, we'll see that they are either fully symmetric (the left half of the string fully matches the right one), or they have one central, unmatched character (as with our "racecar" example).

So, if we keep the track of unmatched characters, this should get us very close to where we want to be.

Since we're dealing with a collection of unique characters, I'm going to use Set as a data structure. So, let's try to reduce our string to a set containing only unmatched characters:

const palindromePerm = s => [...s].reduce(
  (xs, x) => (xs.delete(x) || xs.add(x), xs),
  new Set()
)

palindromePerm('carerac') // Set(1) { 'e' }
palindromePerm('abab') // Set(0) {}

In case it's not clear what's going on - we're first turning the string into an array by using ES6+ spread syntax. Then we're reducing the array into a set containing only unmatched characters by using Set.delete() method which returns true if the value was in the set (otherwise we're adding it to the set).

And this brings us very close to the first working solution - we just need to check if we have 0 or 1 items in our set (to cover both above-mentioned scenarios):

const palindromePerm = s => [...s].reduce(
  (xs, x) => (xs.delete(x) || xs.add(x), xs),
  new Set()
).size < 2

palindromePerm('carerac') //true
palindromePerm('word') //false

It will fail if we try something like this:

palindromePerm('Race car') //false

But we can easily add support for uppercase characters and spaces:

s.toLowerCase().replaceAll(' ', '')

Or more generally, with regex:

s.replace(/[^A-Za-z0-9]/g, '')

I'm going to also add an imperative version in a new post.

Note: I'm using the term "functional" in a relative sense here - JS is not a purely functional language, and using the purely functional, immutable approach here would make these examples more cumbersome.

If you find these type of posts interesting, please let me know (with reactions and/or comments).