Noisy Palindrome: Filtering using ASCII
Because a regular old palindrome just isn’t enough. A walkthrough on how to solve Noisy Palindrome algorithm problem using ASCII in JavaScript
“A regular palindrome would be too easy, right?” — said no one ever.
Well, that’s probably a lie, but you get my point. If you’re like me & investing your time on various sites solving different coding exercises, you’ve more than likely come across the classic palindrome question where it asks you whether a string a palindrome.
In case you haven’t, no worries! The problem that I will introduce in a bit adds just a small layer of complexity to this classic problem, with the solution still covering how we check whether a string is palindrome after we mutate the input.
A palindrome, as a reminder, is a word, phrase, verse, or sentence that reads the same backward or forward. Examples of a palindrome are “madam” and “racecar”. Both of these words read the same whether you go from left-to-right or right-to-left.
So what’s a noisy palindrome? I’m glad you asked — let’s get started!
The Problem
The problem states as follows:
You are given a string s containing lowercase and uppercase alphabet characters as well as digits from “0” to “9”. Return whether s is a palindrome if we only consider the lowercase alphabet characters.
OK — there’s a lot going on there. So not only are we working with alphabet characters in our input string, but we have numbers as well to make things confusing for us. Making matters worse, we also have to worry about uppercase alphabet characters as well! Sheesh.
So what would be a noisy palindrome? Let’s look at a couple of examples:
- “a92bcbXa”
- “4567abcDO”
Our first example is a palindrome. If we’re looking at just the lowercase alphabet characters & remove everything else, our string would look like “abcba”. It reads the same forward & backwards, therefore it’s a palindrome.
Our second example is NOT a palindrome. Again, if we’re looking at just the lowercase alphabet characters & remove everything else, our string would look like “abc”. Because our string does not read the same forward & backwards, it is not a palindrome.
Great! We understand the problem, so how can we approach this?
The Approach
As with any problem, there are quite a few different approaches that we can take with this problem. We can work with the input string as is & come up with a conditional to check whether the current iteration is a lowercase character. That’s definitely a viable solution.
But what if we did all that work upfront and kept our iteration as simple as possible? If we can somehow “clean up” our input string to just contain lowercase alphabet characters, we can save ourselves the trouble of having to check on each iteration as our input would already be just what we expect.
How do we do this? One way is to use whats called an ASCII table.
As defined by ASCII Code, ASCII stands for American Standard Code for Information Interchange. It’s a 7-bit character code where every single bit represents a unique character.
The below table shows the ASCII code for the first 127 numerical characters.
For a more complete ASCII table, visit https://www.ascii-code.com/
If we look more closely at the ASCII table, we see that all of our lowercase characters are conveniently grouped together from 97 to 122. We can use that to our advantage and set a conditional to filter our string to ONLY contain ASCII code between 97 and 122 by using the built-in method, charCodeAt().
Our pseudocode would look something like this:
- Turn our string into an array -> set it to a variable called arr
- Filter our array to only contain lowercase alphabet characters. We’ll use a combination of filter, charCodeAt and ASCII to do this
- Initialize two pointers, with one pointing to the zeroth index and set to 0, while the second pointing to the last index. We’ll call this left and right, respectively.
Remember that we’re checking whether we’re working with a palindrome, so we need to start from the start & finish and work our way inwards.
4. Loop through our newly filtered array and check if the values of the pointers match. If they do, move both pointers towards the middle. Else, return false
5. Return true at the end of our function. If our function reaches the end, we can conclude that our newly filtered array is a palindrome as we completed the loop
The Solution
We’ve laid the groundwork — let’s write some code.
Looking at our pseudocode, our first couple of steps are to turn our input string into an array and then filter our array to only contain lowercase alphabet characters. Let’s do that now:
Using our first test case, we can see that by calling the filter method on our newly created array, we can filter our elements by their ASCII code by calling charCodeAt() on our elements. If their ASCII code falls between 97 and 122 (meaning that they’re a lowercase alphabet character), we keep them in our newArray. If not, they are removed.
Next, we’ll need to initialize our pointers, setting them at the beginning & end of our array.
We now need to somehow loop through our array & have our pointers move towards the middle of the array as we check each value along the way. In this case, a while loop is perfect for our needs, with the condition that it’ll loop until our left pointer meets our right pointer.
If our values match, we’ll continue with the loop. If they do not, we can immediately say that there is no palindrome & break out of the loop, return a false boolean.
Our final solution would look like the following:
Conclusion
And there you have it! What started off as a pretty complicated problem turned out to be pretty manageable. By handling our input string right off the bat & filtering out our unwanted values, we can avoid doing all that logic with each iteration & keep our logic check straightforward.
Understanding how ASCII works can be a powerful tool on your journey as a software developer. Keep it in mind during future coding exercises and/or technical interviews — you never know when it might become useful.
Until next time!
Sources
ASCII-Code: ASCII Code — The extended ASCII table
https://www.ascii-code.com/
