Finding the index of the character whose removal will make a palindrome

Before I get into describing by problem I'd like to point out I found this question under c++ tag. But the solution of that question is already implemented in my code.

I am solving a problem from hackerrank. My code for that problem is logically correct but in some of the cases time limit exceeds.

Problem Statement

Given a string S , of lowercase letters, determine the index of the character whose removal will make a S palindrome. If is already a palindrome or no such character exists, then print -1 . There will always be a valid solution, and any correct answer is acceptable. For example, if S = "bcbc", we can either remove 'b' at index 0 or 'c' at index 3.

Input Format:

The first line contains an integer T , denoting the number of test cases.

Each line i of the T subsequent lines describes a test case in the form of a single string, Si.

Constraints:

Length of the string can be 100005.

Output Format:

Print an integer denoting the zero-indexed position of the character that makes S not a palindrome; if S is already a palindrome or no such character exists, print -1 .

As a solution my code is as following:

import java.io.*;
import java.util.*;

public class Solution {

public static boolean isPalindrom(String s){
    int n = s.length();
    for (int i=0;i0){
        int flag = 0;
        String sb = br.readLine().toString();
        if(isPalindrom(sb)){
            System.out.println("-1");
            flag = 1;
        }
        for(int i=0;i<sb.length()&&flag==0;i++){
            StringBuffer s = new StringBuffer(sb);
            s.deleteCharAt(i);
            if(isPalindrom(s.toString())){
                System.out.println(i);
                break;
            }   
        }
        
    }
}}

I've used best palindrome checker algorithm as described here. and also used BufferedReader as described here. But time limit exceeds in some taste cases. How can I improve my code further?

Thanks in advance!

Code Style

As @coderodde also remarked, you should import specific classes. Wildcard imports are for throw-away code and early development; no later than when your code is approaching completeness, you should replace any then-remaining wildcard imports with specific imports. There are tools that can help you with that.

Also, format your code consistently. Your indentation and placement of spaces are irregular. I find code much easier to read when there are spaces on each side of every binary operator, but if you prefer not to use such spaces then at least be consistent!

I/O

For what it's worth, unlike @coderodde, I have no problem with BufferedReader for your input. For input whose form is so simple, Scanner does not provide much advantage.

Performance

This is the main area of concern, and indeed I do not find it surprising that your code ...

for(int i=0;i<sb.length()&&flag==0;i++){
            StringBuffer s = new StringBuffer(sb);
            s.deleteCharAt(i);
            if(isPalindrom(s.toString())){
                System.out.println(i);
                break;
            }   
        }

... does not perform well. Regardless of the details of the palindrome-checking algorithm, it is performing far more work than it needs to do when used this way. In particular, it is very wasteful to test every deletion candidate, and it is slightly wasteful to test separately whether the full string is already a palindrome. For each string it tests, your code may perform work proportional to the square of the length of the string.

Instead of testing every possible deletion, simply scan each test string from both ends until you find a pair of corresponding characters that differ. If the string can be made a palindrome by deleting a single character, then that character will be one of those two. They are the only candidates you need to consider. By limiting yourself to considering only those as deletion candidates, the maximum amount work performed by your code is only linear in the length of the string. (Also, if every corresponding pair of characters matches, then the string is already a palindrome, so you don't need to perform a separate check for that.)

StackExchange Code Review Q#135009, answer score: 2