/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    private static boolean isPalindrome(char[] data, int left, int right) {
        while (left <= right) {
            if (data[left] != data[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
 
    public static 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");
    }
 
    public static void main(String[] args) {
        String[] candidates = {"abcdedcba", "ablxe was I ere I saw elba"};
        for (String input : candidates) {
            int pos = whichCharForPalindrome(input);
            System.out.printf("Remove '%c' (at %d) from '%s' to make palindrome: %s\n", 
                 input.charAt(pos), pos, input, input.substring(0, pos) + input.substring(pos + 1));
        }
    }
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKICAgIHByaXZhdGUgc3RhdGljIGJvb2xlYW4gaXNQYWxpbmRyb21lKGNoYXJbXSBkYXRhLCBpbnQgbGVmdCwgaW50IHJpZ2h0KSB7CiAgICAgICAgd2hpbGUgKGxlZnQgPD0gcmlnaHQpIHsKICAgICAgICAgICAgaWYgKGRhdGFbbGVmdF0gIT0gZGF0YVtyaWdodF0pIHsKICAgICAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICAgICAgfQogICAgICAgICAgICBsZWZ0Kys7CiAgICAgICAgICAgIHJpZ2h0LS07CiAgICAgICAgfQogICAgICAgIHJldHVybiB0cnVlOwogICAgfQogICAgCiAgICBwdWJsaWMgc3RhdGljIGludCB3aGljaENoYXJGb3JQYWxpbmRyb21lKGZpbmFsIFN0cmluZyBpbnB1dCkgewogICAgICAgIGZpbmFsIGNoYXJbXSBsZXR0ZXJzID0gaW5wdXQudG9DaGFyQXJyYXkoKTsKICAgICAgICBpbnQgbGVmdCA9IDA7CiAgICAgICAgaW50IHJpZ2h0ID0gbGV0dGVycy5sZW5ndGggLSAxOwoKICAgICAgICAvLyBsb29rIGZvciB0aGUgbWlzbWF0Y2g6CiAgICAgICAgd2hpbGUgKGxlZnQgPCByaWdodCAmJiBsZXR0ZXJzW2xlZnRdID09IGxldHRlcnNbcmlnaHRdKSB7CiAgICAgICAgICAgIGxlZnQrKzsKICAgICAgICAgICAgcmlnaHQtLTsKICAgICAgICB9CgogICAgICAgIC8vIE9LLCBpZiB0aGVyZSdzIG5vIGJyb2tlbiBsZXR0ZXIgaW4gdGhpcyBwYWxpbmRyb21lLi4uLgogICAgICAgIGlmIChsZWZ0ID49IHJpZ2h0KSB7CiAgICAgICAgICAgIC8vIHRoZSBkYXRhIGlzIGEgcGFsaW5kcm9tZSwgc28gcmVtb3ZpbmcgKG9uZSBvZikgdGhlIG1pZGRsZSBjaGFycyBpcyBmaW5lLgogICAgICAgICAgICAvLyBzbyByZW1vdmUgdGhlIG1pZGRsZSBvbmUuCiAgICAgICAgICAgIHJldHVybiBsZWZ0OwogICAgICAgIH0KCiAgICAgICAgLy8gcmVtb3ZpbmcgdGhlIGxlZnQgbWFrZXMgYSBwYWxpbmRyb21lLgogICAgICAgIGlmIChpc1BhbGluZHJvbWUobGV0dGVycywgbGVmdCArIDEsIHJpZ2h0KSkgewogICAgICAgICAgICByZXR1cm4gbGVmdDsKICAgICAgICB9CgogICAgICAgIC8vIHJlbW92aW5nIHRoZSByaWdodCBtYWtlcyBhIHBhbGluZHJvbWUuCiAgICAgICAgaWYgKGlzUGFsaW5kcm9tZShsZXR0ZXJzLCBsZWZ0LCByaWdodCAtIDEpKSB7CiAgICAgICAgICAgIHJldHVybiByaWdodDsKICAgICAgICB9CiAgICAgICAgdGhyb3cgbmV3IElsbGVnYWxTdGF0ZUV4Y2VwdGlvbigiV2Ugd2VyZSBzdXBwb3NlZCB0byBiZSBhYmxlIHRvIHJlbW92ZSBhIGNoYXIgIgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICsgInRvIG1ha2UgYSBwYWxpbmRyb21lLCBidXQgY291bGQgbm90Iik7CiAgICB9CiAgICAKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBTdHJpbmdbXSBjYW5kaWRhdGVzID0geyJhYmNkZWRjYmEiLCAiYWJseGUgd2FzIEkgZXJlIEkgc2F3IGVsYmEifTsKICAgICAgICBmb3IgKFN0cmluZyBpbnB1dCA6IGNhbmRpZGF0ZXMpIHsKICAgICAgICAgICAgaW50IHBvcyA9IHdoaWNoQ2hhckZvclBhbGluZHJvbWUoaW5wdXQpOwogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50ZigiUmVtb3ZlICclYycgKGF0ICVkKSBmcm9tICclcycgdG8gbWFrZSBwYWxpbmRyb21lOiAlc1xuIiwgCiAgICAgICAgICAgICAgICAgaW5wdXQuY2hhckF0KHBvcyksIHBvcywgaW5wdXQsIGlucHV0LnN1YnN0cmluZygwLCBwb3MpICsgaW5wdXQuc3Vic3RyaW5nKHBvcyArIDEpKTsKICAgICAgICB9CiAgICB9Cn0=