public class StringPalindrome {
    public static void main(String[] args) {
        String input = "ddabccba";
        System.out.println(solve(input, 0, input.length() - 1));
    }

    public static int solve(String input, int start, int end) {
        if (start == end) return 0;
        if (start > end) return Integer.MAX_VALUE;
        if (start == end - 1) return input.charAt(start) == input.charAt(end) ? 0 : 1;

        return input.charAt(start) == input.charAt(end) ?
                solve(input, start + 1, end - 1) :
                Math.min(solve(input, start + 1, end), solve(input, start, end - 1)) + 1;
    }
}