Interview question: Palindrome detecting algorithm

This is the beginning of what I plan on making a series of posts about programming questions I’ve had during interviews over the years. This first one shows how to create an algorithm for detecting if a string contains a palindrome.

You’re first question maybe, “What’s a palindrome?” and being that you’re in the software engineering field and not an English major makes that a valid question. A quick explanation of a palindrome is that it’s a word that is spelled the same forwards and backwards like the names Bob or Hannah.

Ok. So that seems easy enough. Why would a software company ask you this question in an interview? Well, what if I told you that the string “race car” is also a palindrome. Now knowing this, you can probably begin to see the number of test cases rise and amount of logic needed to correctly handle each one. This is why it’s a good interview question. It shows them how you think and if you can correctly test your own logic.

Let’s begin by defining what this algorithm needs to be able to do.

• Ignore non-alpha characters
• Case insensitive character comparison
• A single letter word like ‘I’ are a valid palindrome
• A string that has no characters to compare is not a valid palindrome
• Return true if the string contains a palindrome and false otherwise

Ok. Let’s get started. How do we go about doing this?

First off, we need to compare the characters in the order of first compares to last, second compares to second to last, and so on. If any of the characters don’t match while doing this, we know it’s not a palindrome. This can be done by having 2 indexes, one that starts from the beginning of the string and another from the end of the string. Each time the indexes point to a character that match, the front index is incremented and the back index is decremented. We loop through this process until the indexes meet or until we find a pair that doesn’t match.

We’re not going to worry too much about comparing the case of the characters. Most languages have a method to either force a character to upper\lower case or to do a non-case sensitive comparison. But you should bring this up to your interviewer just so he\she knows it's on your mind.

boolean IsPalindrome(String givenWord) {

   // Setting the initial index values
   int frontIndex = 0;
   int backIndex = givenWord.length() - 1;
        
   // Moving though all the characters checking for a palindrome
   while (frontIndex <= backIndex) {
            
      // Obtaining characters to compare
      char frontChar = Character.toLowerCase(givenWord.charAt(frontIndex));
      char backChar = Character.toLowerCase(givenWord.charAt(backIndex));
            
      // Do the characters match?
      if (frontChar != backChar)
         return false;
            
      // Preparing for next loop pass
      frontIndex++;
      backIndex--;
   }
  
   //  The word is a palindrome
   return true;
}

Now we have a solution that solves for our sanity cases of Bob and Hannah, but what about “race car”? What we need to do is verify that the front index and the back index point to alphabetical characters before doing the comparison. If an index does not point to a letter, we must increment\decrement it until it does. The thing we have to be aware of while doing this is that we don’t want our indexes to pass each other.

// Trying to find an alpha character by moving left to right
while (!Character.isLetter(givenWord.charAt(frontIndex)) && frontIndex < backIndex)
   frontIndex++;
char frontChar = Character.toLowerCase(givenWord.charAt(frontIndex));

// Trying to find an alpha character by moving right to left
while (!Character.isLetter(givenWord.charAt(backIndex)) && frontIndex < backIndex)
   backIndex--;
char backChar = Character.toLowerCase(givenWord.charAt(backIndex));

Things are looking pretty good, but what about the test case for a string that contains no letters like “1337”? Your first reaction would probably be to add a check after setting frontChar to verify that it’s a letter and return false if it isn’t. This is partially correct. The problem is that a string like “a7a” is a valid palindrome and adding this check alone would not allow this test case to pass. What is also needed is a way to indicate that no other alphabetical pairs have matched before returning false. Adding a Boolean value that is initially set to false can do this. When a matching character pair has been found, this value will be set to true. This way we will only return false if we come across a frontChar that is not a letter and no previous matches have been found.

// Checking to make sure the character is an alpha character and if it isn't, checking to 
// see if a previous match has been found already.
if (!Character.isLetter(frontChar) && !matchFound)
   return false;

...

// Preparing for next loop pass
frontIndex++;
backIndex--;
matchFound = true;

Great! All we need now is to put everything together, add a string is NULL and\or 0 length check at the beginning of the method, and you have a working palindrome algorithm detector.

You can view the full algorithm code here.

Comments

[Freddy Y]

No, not going to work with "if a string 'contains' a palindrome", which was the question you posted. This solution only works for "if the string 'is' a palindrome". Try "abcddcbw".