STREDUCE - String reduction

Given a string containing only characters of 'a' and 'b'. You can reduce this string by replacing a substring forming a?a or b?b by ?; ? is 'a' or 'b'.

Request

Find a way to minimize the length of given string by reducing it. Output that minimum length.

Input

- A string.

Output

- The minimum length found.

Example

Input:
baaba

Output:
1

Limitations

- The length of the given string does not exceed 300.


Added by:AnhDQ
Date:2009-06-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:NEERC 2001 - Western Subregion

hide comments
2009-08-20 10:59:49 gawry
The input seems to contain some strange white characters, do not use gets.
2009-08-20 10:59:49 Seckin Can Sahin
in the example,
baaba -> bab -> a

(aba -> b, and then bab ->a)
2009-08-20 10:59:49 ahmed mamdouh [devils13]
what is the meaning of
"a?a or b?b by ?; ? is 'a' or 'b'" ?

Re: it means you have 4 operator:
aaa>>a
aba>>b
bab>>a
bbb>>b

ok ;)


Last edit: 2009-07-12 03:29:14
2009-08-20 10:59:49 Carlos Eduardo Rodrigues Alves [USJT]
Only one string in the input.

Last edit: 2009-06-28 04:03:56
2009-08-20 10:59:49 Karpovych Artem
what input should be in this problem?
Only one string?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.