Category: Data-Structures and Algorithms

To read the full prompt, navigate to HackerRank Palindrome Index Question.

The core of this question is determining whether or not an input string is a palindrome in its current orientation or determining the index of a character that could be removed to make the input string a palindrome.

Here are some examples that Hackerrank provides:

Test Case 1: "aaab"
Removing 'b' at index 3 results in a palindrome, so we print on a new line.

Test Case 2: “baa”
Removing ‘b’ at index 0 results in a palindrome, so we print on a new line.

Test Case 3: "aaa"
This string is already a palindrome, so we print -1; however, 0, 1, and 2 are also all acceptable answers, as the string will still be a palindrome if any one of the characters at those indices are removed.

The naive implementation is to remove every single character while constructing a new string every iteration and checking whether the new string is a palindrome. This implementation is slow and we can do better.

For a string to be a palindrome, we know that the string must be reversible. In other words, every character leading up to the length of the string divided two must have a corresponding character on the opposite side of the string. We don’t have to worry about when an input string’s length is odd because the middle character reversed would always be itself. With this knowledge, we know we can solve this problem iterating through the first half of characters and compare them to the second half of characters. As soon as we hit a pair of characters not equal, we know that one of the two characters can be removed from the original input string to form a palindrome. We only have to check that one of the characters is a palindrome due to the requirements dictating that there will always be a valid solution.

In this instance, checking if a string is a palindrome is a little more difficult than usual because we must take into account the index to exclude. To do this, we iterate through the length of the string divided two and compare the first half of characters to the second half of characters. The character that needs to be excluded is just skipped over. Alternatively, one could simply copy the string and then check the reverse order property but that would be a waste of memory.

Here is my Java solution to this problem:

public class Solution {
    /**
    * Determines if a string is a palinderome while excluding a character denoted  index. This prevents
      us from having to make another string which is the exact same as the original string
      excluding the 'indexToExclude' argument. 
    *
    *
    **/
    private static boolean isPalindrome(String possiblePalindrome, int indexToExclude){
        int halfOfStringLength = possiblePalindrome.length() / 2;
        for(int i = 0; i < halfOfStringLength; i++){
            int firstHalfIndex = i;
            int secondHalfIndex = possiblePalindrome.length() - i - 1;
            
            if(firstHalfIndex >= indexToExclude){
                firstHalfIndex += 1;
            }
            if(secondHalfIndex <= indexToExclude){
                secondHalfIndex -= 1;
            }
            if(possiblePalindrome.charAt(firstHalfIndex) != possiblePalindrome.charAt(secondHalfIndex)){
                return false;
            }
        }
        return true;
    }
    /**
    *@return the index of the character that needs to be removed to make a palindrome. Note that if the string is already in palindrome orientation, then -1 will be returned.
    *
    **/
    private static int getPalindromeIndex(String possiblePalindrome){
        int halfOfNextLineLength = possiblePalindrome.length() / 2;
        for(int j = 0; j < halfOfNextLineLength; j++){
            int secondHalfIndex = possiblePalindrome.length() -  j - 1;
            if(possiblePalindrome.charAt(j) != possiblePalindrome.charAt(secondHalfIndex)){
                if(isPalindrome(possiblePalindrome, j)){
                    return j;
                } else {
                    return secondHalfIndex;
                }
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String numberOfInputs = scanner.nextLine();
        
        for(int i = 0; i < Integer.valueOf(numberOfInputs); i++){
            String next = scanner.nextLine();
            System.out.println(getPalindromeIndex(next));
        }
        scanner.close();
    }
}

Do you see a faster way to do this? Comment below!