recursion - String Reduction - Programming Contest . Solution needed

Question

I have a question which asks us to reduce the string as follows.

The input is a string having only A, B or C. Output must be length of the reduced string

The string can be reduced by the following rules

If any 2 different letters are adjacent, these two letters can be replaced by the third letter.

Eg ABA -> CA -> B . So final answer is 1 (length of reduced string)

Eg ABCCCCCCC

This doesn't become CCCCCCCC, as it can be reduced alternatively by

ABCCCCCCC->AACCCCCC->ABCCCCC->AACCCC->ABCCC->AACC->ABC->AA

as here length is 2 < (length of CCCCCCCC)

How do you go about this problem?

Thanks a lot!

To make things clear: the question states it wants the minimum length of the reduced string. So in the second example above there are 2 solutions possible, one CCCCCCCC and the other AA. So 2 is the answer as length of AA is 2 which is smaller than the length of CCCCCCCC = 8.

Answer 1

The way this question is phrased, there are only three distinct possibilities:

1. If the string has only one unique character, the length is the same as the length of the string.

2/3. If the string contains more than one unique character, the length is either 1 or 2, always (based on the layout of the characters).

Edit: As a way of proof of concept here is some grammar and its extensions: I should note that although this seems to me a reasonable proof for the fact that the length will reduce to either 1 or 2, I am reasonably sure that determining which of these lengths will result is not as trivial as I originally thought ( you would still have to recurse through all options to find it out)

S   :   A|B|C|()
S   :   S^

where () denotes the empty string, and s^ means any combination of the previous [A,B,C,()] characters.

Extended Grammar:

S_1 :   AS^|others
S_2 :   AAS^|ABS^|ACS^|others
S_3 :   AAAS^|
        AABS^ => ACS^ => BS^|
        AACS^ => ABS^ => CS^|
        ABAS^ => ACS^ => BS^|
        ABBS^ => CBS^ => AS^|
        ABCS^ => CCS^ | AAS^|
        ACAS^ => ABS^ => CS^|
        ACBS^ => AAS^ | BBS^|
        ACCS^ => BCS^ => AS^|

The same thing will happen with extended grammars starting with B, and C (others). The interesting cases are where we have ACB and ABC (three distinct characters in sequence), these cases result in grammars that appear to lead to longer lengths however:

CCS^:   CCAS^|CCBS^|CCCS^|
        CBS^ => AS^|
        CAS^ => BS^|
        CCCS^|
AAS^:   AAAS^|AABS^|AACS^|
        ACS^ => BS^|
        ABS^ => CS^|
        AAAS^|
BBS^:   BBAS^|BBBS^|BBCS^|
        BCS^ => AS^|
        BAS^ => CS^|
        BBBS^|

Recursively they only lead to longer lengths when the remaining string contains their value only. However we have to remember that this case also can be simplified, since if we got to this area with say CCCS^, then we at one point previous had ABC ( or consequently CBA ). If we look back we could have made better decisions:

ABCCS^  =>  AACS^   =>  ABS^    =>  CS^ 
CBACS^  =>  CBBS^   =>  ABS^    =>  CS^

So in the best case at the end of the string when we make all the correct decisions we end with a remaining string of 1 character followed by 1 more character(since we are at the end). At this time if the character is the same, then we have a length of 2, if it is different, then we can reduce one last time and we end up with a length of 1.