Palindrome? How is it relevant to you as a developer?
What is a Palindrome?
A Palindrome is a sequence of character, phrase, or even a block of text that can be spell/read the same backward and forward.
For example of Palindromes and Non Palindromes:
‘Poop’ == True
‘Civic’ == True
1122 == False
‘A car, a man, a maraca’ == True
In this post, I will explain how to identify Palindromes and the underlying structures of Palindromes as well as some of the simple solutions examples in Python.
The Simple Solutions To a Simple Problem
So how would one approach a question like this? How can you write a program that will identify if a given string is a palindrome?
Luckily, there are multiple ways to deal with these problem and they’re all more or less as simple as one would think.
The Cheating Way
The solution will take the original string, reverse it by using python slicing syntax. The [:] means to start from the beginning to the end index. If there is no value in front of the first colon, start at the very beginning of the list. If there’s no value after the first colon, it also mean to go to the end of the list. The -1 stuck behind [::-1] just means to increment the index of the list by negative 1 every time you traverse through the list.
For example:
(‘hello’)[::-1] will return back a string of ‘olleh’
(‘hello’)[::-2] will return back a string of ‘olh’ ← Increment of 2
Iteratively With For Loop
There are typically multiple ways to solve this problem iteratively but two simple way that is easy to read and implement is with slicing and regular indexing.
The first solution takes in a string and loop over the floor division of the length of given string. This will make sure it will never go to the middle letter if there are any. The loop will compare the value of string index ‘i’ and ‘-i’ every loop and there is a -1 because index start at 0.
This solution might be easier to understand for beginner because there is a clear left and right index variable. The concept is still the same as above. We are not trying to compare the middle index because they do not matter in a palindrome so left < right is good enough.
Recursively Palindrome
Recursion are typically hard to visualize but are great solution to string manipulation and searching algorithms.
These two solution may look like they’re similar but make no mistake, they are completely different under the hood.
The first solution base case will check if the remaining string is longer than 1, if not then return true because all letter match. However, this solution is vastly inferior to the indexing recursion method because space complexity. This solution’s return call will break down the string into smaller string and create a new list of character every time it is call with one less character in the beginning and one less at the end. What you can assume is that when it’s called, it will create new array in memory for a new string. e.g. if you enter in ‘civic’, the function will call it like this ‘civic’ → ‘ivi’ → ‘v’. Now there are three different string in memory instead of one. Imagine a palindrome with over 100 character, it will have to break down that string and create a new string 50 times before it returns true.
The second solution may look more daunting and longer but it will create less problem for you in the long run. Instead of slicing part of the string each call, the statement will only compare the position of the character in the string using their index instead. This will create no other string in memory and is faster in a scaling sense. Every time we call the function again, we will just need to add and subtract 1 to left and right index and pass those value in for the next call to use. Not only this is much better space wise, it is more readable and easy to understand for others.
Underlying Structure of Palindromes
Now that we can identify if a sequence is a palindrome or not, lets take it to the next level.
We all know what a palindrome is, but what if we want to know if a sequence have the potential to be a palindrome? That’s right, we’re talking about Palindromes and its Permutation. How do we know if the word ‘aaabbb’ or ‘racecar’ have the potential to be a permutation depending on how its arrange?
What is a permutation?
A simple and plain description of permutation is all the ways of doing something. Or all the ways you can rearrange something. Using factorial, it is easy to understand how many permutation a sequence(string) can fit together. For example, the word ‘boy’, while having three letters can have up to 6 combination so the factorial is
3! = 3 * 2 * 1 = 6
Palindrome or Not?
You can start to see how this can be a problem when trying to brute force a way to find if a permutation of a sequence will make up a palindromes. The more character the sequence have, the exponentially larger it gets! If we try to check the phrase ‘ A nut for a jar of tuna’, that is equal to 17! or 17 factorial which is ~355 trillion combination of letters. Using a loop method will take an excruciating long run-time in a worst case scenario to find out if a sequence is a palindrome by cross checking each combination. However! We do not need to do any of that, that’s just too much work!
Palindrome Structure
For the next part, we want to think about the underlying structure of a palindrome. What makes a palindrome a palindrome?
This question is equivalent to asking what make a sandwich a sandwich? Well, a standard sandwich have two pieces of bread, some veggies, and some form of meat. Palindromes are the same, it comes with set formula to determine if it is a palindrome or not. Take some time to think about it and keep on reading.
Here it is, a string palindrome almost always come with any amount of even number of unique character AND 1 or less odd number of unique character.
Confused? Don’t be, heres an example:
Ex 1:
'aabb' == TrueNo. of 'a' = 2 <- Even
No. of 'b' = 2 <- EvenPalindrome Sequence = 'baab' or 'abba'Ex 2:
'aaabb' == TrueNo. of 'a' = 3 <- odd
No. of 'b' = 2 <- evenPalindrome Sequence = 'baaab' or 'ababa' (we do not care for middle letter because it can be anything it wants)Ex. 3:
'abbccddd' == FalseNo. of 'a' = 1 <- odd
No. of 'b' = 2 <- even
No. of 'c' = 2 <- even
No. of 'd' = 3 <- oddNo palindrome sequence will be found because there are more than 2 odd number of character
The Solution
The easy solution for this would be counting unique letter for the string and condition the code to return false if the number of odd character is more than one. You can use a HashMap or a dictionary(histogram) to store these key-value pair e.g. ‘aabb’ → {a: 2, b: 2} and check those key-value afterward.
The solution above is very straight forward, you have a dictionary, and you will count up unique character and add them as key-value pair in the dictionary. After all the character is added, you will count how many odd value are there and will return false if there is more than two. Here is more accurate visualization and process of the function.
Time-Complexity: O(n). We traversing through the string and again with the dictionary.
Space-Complexity: O(n). Dictionary can grow up to size n
Conclusion
Whether this have any real life application or not is up to you decide but Palindromes are something developers should be somewhat familiar with as they are common technical interview questions because it involve string manipulation, traversal, reversal, optimization.
