Possible Palindrome check from given string - efficient code needed

Question

I am solving Palindrome index problem. The problem's difficulty level is easy and still I didn't pass all testcases :(. At most of the testcases, I got timeout and surprisingly one testcase failed as well. I googled about palindrome checking - there seems to be just two ways-

1. Using StringBuilder reverse() method.
2. Comparing characters till mid of the string length.

I tried both approaches and still no success.

Following is my attempt:

import java.util.Scanner;

public class PalindromeIndex {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int totalTestCases = Integer.parseInt(scanner.nextLine());

        String testString = null;
        StringBuffer outputString = new StringBuffer();
        for (int i = 0; i < totalTestCases; i++) {
            testString = scanner.nextLine();
            boolean is0thElementTrue = false;
            // One lettered word is always a palindrome so checked that
            // condition
            if (isPalindrome(testString) || testString.length() == 1) {
                outputString.append("-1");
            } else {
                if (isPalindrome(testString.substring(1))) {
                    outputString.append("0 ");
                    is0thElementTrue = true;
                }
                // See here j - index starts from 1 as initial case is
                // already
                // handled in above if-condition
                // Also see the condition checks [j < testString.length() -
                // 1;]
                // because (testString.length() - 1) is checked separately
                // after
                // this for loop.;
                boolean isLoopSuccessAtleastOnce = false;
                for (int j = 1; j < testString.length() - 1; j++) {
                    if (isPalindrome(testString.substring(0, j)
                            + testString.substring(j + 1, testString.length()))) {
                        isLoopSuccessAtleastOnce = true;
                        if (is0thElementTrue) {
                            outputString.append(j);
                            is0thElementTrue = false;
                        } else
                            outputString.append(" " + j);
                    }
                }
                if (isPalindrome(testString.substring(0,
                        testString.length() - 1))) {
                    if (isLoopSuccessAtleastOnce)
                        outputString.append(" " + (testString.length() - 1));
                    else
                        outputString.append((testString.length() - 1));
                }
            }
            outputString.append("\n");
        }
        System.out.println(outputString.toString());
        scanner.close();
    }

    private static boolean isPalindrome(String str) {
        StringBuilder strBuffer = new StringBuilder(str);
        return str.equalsIgnoreCase(strBuffer.reverse().toString());
    }

    private static boolean isPalindrome_2ndWay(String str) {
        int n = str.length();
        for (int i = 0; i < (n / 2) + 1; ++i) {
            if (str.charAt(i) != str.charAt(n - i - 1)) {
                return false;
            }
        }

        return true;
    }
}

Answer 1

Your solution is quadratic, this is definitely not what that site is looking for, you can do much better.

Consider this. If the first and last characters are not equal to each other, then one of them is the answer. If they are equal, the same logic can be applied to second and one before last characters. Etc.