Palindromes without character

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 co

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:

-
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.

-
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.

StackExchange Code Review Q#77740, answer score: 5