STREDUCE - String reduction
English | Tiếng Việt |
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 !
|
|
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.
|
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 |