| Submit | All submissions | Best solutions | Back to list |
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.
| 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
|
|||||
|
2016-02-11 14:15:00 Utkarsh Agarwal
can answer be anything different than 1, 2 or length ?? if yes case pls |
|||||
|
2015-03-30 14:59:10 Sudharsansai
Very nice question.... |
|||||
|
2014-10-16 07:34:31 vishal johri
I am getting WA even though my solution looks correct! ..Kindly post some tricky testcases so that I can verify my answer..Thanks! |
|||||
|
2012-06-17 18:42:10 amit
tough!! Last edit: 2012-06-17 18:42:48 |
|||||
|
2012-04-04 17:38:30 Samiul Saeef
n^3 dp AC passes in 3.11 sec |
|||||
|
2011-11-07 23:17:13 M Misbachul Huda
I still geting WA, please help me ! :( please give me more testcase |
|||||
|
2011-10-20 09:41:48 Supreeth
O(n*8) worked |
|||||
|
2011-02-13 13:51:27 Prabakaran
will O((n^3)*25) solution pass? |
|||||
|
2011-01-17 16:14:06 sudipto das
Pawel Gawrychowski is right...After getting several WA, i noticed his post and finally got ac... So,DONT USE GETS(). |
|||||
|
2009-08-20 10:59:49 [Trichromatic] XilinX
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 |
|||||
RSS