题目描述

所谓回文串就是正读和反读都一样的字符串。给定一个字符串，通过删除若干字符，都可以变成回文词。请计算最少删除多少字符才能够让给定的字符串变成回文。

输入格式

• 一个字符串：表示给定的字符串 $s$，保证 $s$ 完全由小写字母构成。

输出格式

• 单个整数：表示最少删除多少字符可以让给定的字符串变成回文。

iai

0

样例解释 1

不需要删除任何字符

aab

1

样例解释 2

删除b

数据范围

记 $n$ 为输入字符串的长度，

• 对 $30\%$ 的数据，$1\leq n\leq 20$
• 对 $60\%$ 的数据，$1\leq n\leq 500$
• 对 $100\%$ 的数据，$1\leq n\leq 2000$