1737 - 最长回文

1737 - 最长回文

Description

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

Input

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

Output

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

Examples

Input

ywczzc

Output

Input

aab

Output

Hint

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

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

Tags

区间DP 动态规划字符串普及+

题目参数

Time Limit	1 second
Memory Limit	128 MB
提交次数	38
通过次数	7

Stats

题解

上一题

下一题