What are palindromes?

The formal definition of a palindrome is a word that reads the same way forwards or backwards. Some examples would be the words “pop”, “tot” or “civic”. Numbers, names, words, magic word squares, dates, musical and variations, such as ignoring punctuation or other characters can also be palindromes. When researching this topic I was surprised to learn how rich the history of this was and I learned that it dates back to the ancient Greeks because the Greek word palin means back and dromos means direction [2], [3].

How is this relevant to my life?

If you are a developer you may have run into this type of interview question already. If you are new to this field it can be intimidating if you have not prepared for a code interview like the ones I am referring to. Tech companies seem to delight in putting candidates through multiple mind game style interview sessions because I guess it is quite the ego trip. I myself have encountered this one on almost every interview I have been to. It is important to know how to explain what this is, how to implement it on the white board and in a virtual coding interview. In the medical field palindromes are seen inside of DNA which have nucleotides sequences which read the same from 5′-end to the 3′-end [4]. Other than what I described above knowing about this is probably not useful unless it came up on some game show for a substantial amount of money or some kind of small talk at get togethers or dinner parties.

Complexity Analysis

As simple as a palindrome seems, we can actually analyze how long an iterative algorithm implementation would run. If you had N characters from a word you can complete it in the worst case in O(N). The reason for this is you would only need one for loop as explained above and work your way from the ends towards the middle.

Real Examples

As I was preparing for this article I found it interesting how many ways a developer could implement an algorithm to determine if a word is a palindrome or not. The following are just a few of the ones I either figured out on my own or adapted from various sources.

Trivial example in C# for lulz

bool isPalindrome = false;
var word1 = "tot";
var word2 = word1.Reverse();

if(word1.SequenceEqual(word2))
{
   isPalindrome = true;
}

Interface implementation variation 1 

//Interface defined in a different file but provided as 
//reference

 public interface IPalindromeInputCheck<TInput>
 {
     bool IsPalindrome(TInput input);
 }

//We are implementing the interface as part of the Strategy
//Design pattern.
public class CheckPalindromeReverseMethod : IPalindromeInputCheck<string>
    {
        public bool IsPalindrome(string input)
        {
            if (input is null)
            {
                throw new ArgumentNullException(nameof(input));
            }

            var isPalindrome = false;
            
            var word2 = input?.Reverse();

            if (input.SequenceEqual(word2))
            {
                isPalindrome = true;
            }

            return isPalindrome;
        }
    }

Extension method alternative variation 1

public static class PalindromeExtensions
{
   public static bool IsPalindrome(this string input) 
   {
        if (input is null)
        {
            throw new ArgumentNullException(nameof(input));
        }

        var isPalindrome = false;

        var word2 = input?.Reverse();

        if (input.SequenceEqual(word2))
        {
           isPalindrome = true;
        }

        return isPalindrome;
    }
}

......
//this allows you to use the IsPalindrome method on types such 
//as the string input 
//without having to instantiate an interface.

string input = "abc";

// Act
var result = input.IsPalindrome();

[1] Anonymous, “Anagrams” retrieved from https://www.yourdictionary.com/anagram

Accessed 4 July 2023

[2] Anonymous, “Palindromes” retrieved from https://www.yourdictionary.com/palindrome

Accessed 4 July 2023

[3] Britannica, The Editors of Encyclopedia. “palindrome”. Encyclopedia Britannica, 27 Jun. 2019, https://www.britannica.com/art/palindrome. Accessed 2 July 2022.

[4] Giel-Pietraszuk M, Hoffmann M, Dolecka S, Rychlewski J, Barciszewski J. Palindromes in proteins. J Protein Chem. Retrieved from https://pubmed.ncbi.nlm.nih.gov/12760415/ 2003 Feb;22(2):109-13. doi: 10.1023/a:1023454111924. PMID: 12760415.