思路: 动态规划

$dp[i]$ 表示前 i 个字符，使得串成为好串的最小删除数

对于第 $i$ 个字符，可以选择删除或者不删除。

如果删除第 $i$ 个字符：$dp[i]=dp[i-1]+1$
如果不删除第 $i$ 个字符，需要有第 $j$ 个字符满足 $s[j]=s[i], j<i$ 且 $j$ 尽可能大 ，即 $dp[i]=dp[j-1]+i-j-1$

两者取最小值即可。

题目内容

小红有一个字符串，现在他想问你，最少需要删掉多少个字符，才可以使字符串变成一个好串。

对于小红来说，一个好串的长度必须是偶数，且满足当串的下标从 $0$ 开始，那么当 $i$ 是偶数，都有 $s_i=s_{i+1}$。

输入描述

一行，一个字符串，字符串长度不超过 $10^5$。

字符串只包含小写字母。

输出描述

一个数，表示最少需要删除的字符数量，才能使得字符串变为一个好串。

样例

输入

abbcdd

输出

2

说明

删除 a 和 c 后，字符串变为了 bbdd ，是一个好串。