1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
string=raw_input()
n = len(string)
dp = [[0]*n for _ in range(n)]
for ii in range(n)[::-1]:
    for jj in range(ii,n):
        #print ii,jj
        if jj==ii+1 :
            if string[ii]==string[jj]:
                dp[ii][jj] = 0
            else:
                dp[ii][jj] = 1
                
        else:
            if string[ii]==string[jj] and ii+1<=n-1 and jj-1>=0:
                dp[ii][jj]=dp[ii+1][jj-1]
            else:
                if ii+1<=n-1 and jj-1>=0:
                    dp[ii][jj]=min(dp[ii+1][jj],dp[ii][jj-1],dp[ii+1][jj-1])+1
print dp[0][-1]
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX