Palindrome Index

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

Input Format

The first line contains an integer, T, denoting the number of test cases. Each line i of the T subsequent lines (where 0 <= i < T ) describes a test case in the form of a single string,Si .

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 .

Sample Input

  3
  aaab
  baa 
  aaa
 

Sample Output

  3
  0
 -1
 

Explaination

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 , 2 and are also all acceptable answers, as the string will still be a palindrome if any one of the characters at those indices are removed.

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

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        for(int i=0; i < q; i++)
        {
            StringBuilder sb = new StringBuilder(sc.next());
            int l = sb.length();
            boolean flag = false;   
            for(int j =0; j < l/2 ; j++)
            {
               if(sb.charAt(j) != sb.charAt(l -j- 1))
                 {
                   int index = getIndex(sb, j , l -1 -j);
                   System.out.println(index);
                   flag = true;
                   break;
                 }  
            }
            if(!flag)
             System.out.println("-1");    
        }    
    }
    
    public static int getIndex(StringBuilder sb, int i, int j)
      {
         StringBuilder s1 = new StringBuilder(sb);
         StringBuilder s2 = new StringBuilder(sb);
         s1.deleteCharAt(i);
         s2.deleteCharAt(j);
         String s3 =  s1.toString();
         String s4 = s2.toString();
        if(s3.equals(s1.reverse().toString()))
          {       
           return i;
         }  
         else
          {   
           return j;
         }
      } 
}