STREDUCE - String reduction

no tags 

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.


hide comments
Utkarsh Agarwal: 2016-02-11 14:15:00

can answer be anything different than 1, 2 or length ?? if yes case pls

Sudharsansai: 2015-03-30 14:59:10

Very nice question....

vishal johri: 2014-10-16 07:34:31

I am getting WA even though my solution looks correct! ..Kindly post some tricky testcases so that I can verify my answer..Thanks!

amit: 2012-06-17 18:42:10

tough!!

Last edit: 2012-06-17 18:42:48
Samiul Saeef: 2012-04-04 17:38:30

n^3 dp AC passes in 3.11 sec

M Misbachul Huda: 2011-11-07 23:17:13

I still geting WA, please help me !
:(
please give me more testcase

Supreeth: 2011-10-20 09:41:48

O(n*8) worked

Prabakaran: 2011-02-13 13:51:27

will O((n^3)*25) solution pass?

sudipto das: 2011-01-17 16:14:06

Pawel Gawrychowski is right...After getting several WA, i noticed his post and finally got ac... So,DONT USE GETS().

[Trichromatic] XilinX: 2009-08-20 10:59:49

I've found that this problem originally comes from NEERC 2001, Western Subregion.

Re: Yes, I confirm your information right! I will alter the problem and the source suitably, sorry for the inconvenience.

Last edit: 2009-08-20 10:57:08

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