Palindromes without character

Question

You are given a string of lowercase letters. Your task is to figure out the index of the character whose removal will result in a palindrome. There will always be a valid solution.

Here is my quick solution:

public class Main {

    private static final String AAA = "aaa";

    public static void main(String[] args) {
        System.out.println(palindromeIndex(AAA));
    }

    /**
     * Returns whether a word is palindromic or not
     * @param word
     * @return true if the word is palindromic, false otherwise
     */
    public static boolean isPalindrome(String word) {
        return word.equals(new StringBuffer().append(word).reverse().toString());
    }

    public static int palindromeIndex(String word) {
        if(isPalindrome(word)) {
            return -1;
        }

        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < word.length(); i++) {
            sb.append(word);
            sb.deleteCharAt(i);
            if(isPalindrome(sb.toString())) {
                return i;
            }
            sb.delete(0, word.length());
        }

        /**the question said that there will always be a valid answer
         * so this shouldn't be necessary
         */
        return - 1;
    }
}

Additionally, out of a little dissatisfaction, I came up with an alternative method of figuring out whether a word is a palindrome:

public static boolean isPalindromeAlt(String word) {
    char[] chars = word.toCharArray();
    int wordEnd = word.length() - 1;
    for(int i = 0; i < chars.length; i++) {
        if(chars[i] != chars[wordEnd]) {
            return false;
        }
        wordEnd--;
    }

    return true;
}

But my question is, after actually thinking about it, is the way I have handled the palindrome index part efficient? I don't really like the fact that I am clearing a the stringbuffer after each iteration and using one, I thought that it might be more efficient to use an array or something, could someone please comment on whether my solution is efficient and whether there could be a more efficient way.

I could probably write a more efficient one in Python, I like how Strings are handled as arrays in it.

Answer 1

Your code could be simplified significantly if you remove your checking algorithms, and work off only the assumptions and facts given.

What can we say about the inputs?

1. it is a string of lower case letters
2. with the removal of a single character, it will be a palindrome.
3. there is a character to remove.

Your use of StringBuilders and other systems to build and verify these facts is overkill.

Bug

You have slightly misinterpreted the requirements. Note, that a valid palindrome as an input string will always also have a char that can be removed leaving another valid input string.

If the palindrome input has an odd number of characters, then removing the middle one leaves a valid palindrome. If it has an even number then removing one of the two middle ones leaves a valid solution too.

Your code fails to handle this gracefully, and returns -1.

Primitives

Working with primitives is almost always my first choice. In this case, char[] arrays are better than Strings, StringBuffers, and StringBuilders.

I note in your code you use a StringBuffer. This is a poor choice in almost any modern context. When you encounter a StringBuffer you should always question whether it should instead be a StringBuilder.

Simpler Palindrome check

Consider the simpler code:

private boolean isPalindrome(char[] data, int left, int right) {
    while (left <= right) {
        if (data[left] != data[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

OK, the above code will check whether the characters between two points make up a palindrome. Note that it does not need any new memory structures like StringBuilders, Strings, etc.

Putting it together

How would you use that? Well, consider this outer loop:

public int whichCharForPalindrome(final String input) {
    final char[] letters = input.toCharArray();
    int left = 0;
    int right = letters.length - 1;

    // look for the mismatch:
    while (left < right && letters[left] == letters[right]) {
        left++;
        right--;
    }

    // OK, if there's no broken letter in this palindrome....
    if (left >= right) {
        // the data is a palindrome, so removing (one of) the middle chars is fine.
        // so remove the middle one.
        return left;
    }

    // removing the left makes a palindrome.
    if (isPalindrome(letters, left + 1, right)) {
        return left;
    }

    // removing the right makes a palindrome.
    if (isPalindrome(letters, left, right - 1)) {
        return right;
    }
    throw new IllegalStateException("We were supposed to be able to remove a char "
                                  + "to make a palindrome, but could not");
}

Note that this is an O(n) operation, it scales well, and it tolerates working palindrome input too.

I put this in to an Ideone here.

Answer 2

The time complexity of your solution is O(n ^ 2), where n is the length of the given string. It is possible to do much better. Here is a linear solution:

static int getPalindromeIndex(String word) {
    if (isPalindrome(word))
        return -1;
    // Finds the first pair of characters that don't match.
    int left = 0;
    int right = word.length() - 1;
    while (word.charAt(left) == word.charAt(right)) {
        left++;
        right--;
    }
    // One of them must be removed and it sufficient to remove one of them.
    if (isPalindrome(word.substring(0, left) + word.substring(left + 1)))
        return left;
    return right;
}

The idea is the following:

1. If it is not a palindrome, there is a pair of positions (i, n - i - 1) such that characters on this positions do not match.

2. We can remove one of them. It is guaranteed that a solution always exists so we can try to remove the first one and check if a string is a palindrome. If it is the case, then we can just return it. Otherwise we can just return the second one.