There is some basic structure that can be used to solve this problem in O (n) time.
The above rules are (most) rules defining a mathematical group, in particular the group D_2, sometimes also known as K (for four Klein groups) or V (German for Viergruppe, four groups). D_2 is a group with four elements, A, B, C and 1 (single element). One of the implementations of D_2 is the set of symmetries of a rectangular box with three different sides. A, B and C - rotation of 180 degrees along each of the axes, and 1 - rotation of the identity (without rotation). The group table for D_2 is
|1 ABC -+------- 1|1 ABC A|A 1 CB B|BC 1 A C|CBA 1
As you can see, the rules correspond to the rules specified in the task, except that the rules associated with 1 are not present in the task.
Since D_2 is a group, it satisfies a number of rules: closure (the product of any two elements of the group is another element), associativity (which means (x*y)*z = x*(y*z) for any elements x , y , z , i.e., the order in which the lines are shortened does not matter), the existence of identity (there is an element 1 such that 1*x=x*1=x for any x ) and the existence of the converse (for any element x such an element x^{-1} such that x*x^{-1}=1 and x^{-1}*x=1 , in our case each element is its own inverse).
It is also worth noting that D_2 is commutative , i.e. x*y=y*x for any x,y .
For any row of elements in D_2, we can greedily reduce to one element in a group . For example, ABCCCCCCC=CCCCCCCC=CCCCCC=CCCC=CC=1 . Please note that we do not write element 1 , unless it is the only element in the row. Associativity tells us that the order of operations does not matter, for example, we could work from right to left or start in the middle and get the same result. Try right: ABCCCCCCC=ABCCCCC=ABCCC=ABC=AA=1 .
The situation is different from the fact that operations from 1 not allowed, so we cannot just exclude pairs AA , BB or CC . However, the situation is not so different. Consider the string ABB . We cannot write ABB=A in this case. However, we can eliminate BB in two steps using A : ABB=CB=A Since the order of work does not matter by associativity, we are guaranteed to get the same result. Therefore, we cannot go from ABB to A , but we can get the same result on a different route.
Such alternative routes are available if there are at least two different elements in the line. In particular, in each of ABB , ACC , BAA , BCC , CAA , CBB , AAB , AAC , BBA , BBC , CCA , CCB , we can act as if we have a reduction xx=1 , and then discard 1 .
It follows that any string that is not uniform (not every letter) and has a two-letter substring ( AA , BB , or CC ) can be reduced by removing the double letter. Lines containing only two identical letters cannot be further reduced (because 1 not resolved in the problem), therefore it seems safe to assume that any heterogeneous line can be reduced to A , B , C , AA , BB , CC .
We still have to be careful, because CCAACC could be turned into a converter by removing the middle pair AA , but this is not the best we can do: CCAACC=AACC=CC or AA takes us to a string of length 2.
Another situation that we must be careful about is AABBBB . Here we could exclude AA to finish with BBBB , but first it’s better to remove middle B , then anything: AABBBB=AABB=AA or BB (both of which are equivalent to 1 in the group, but cannot be further reduced in the problem).
There was another interesting situation: AAAABBBB . Blind pair removal leads us to AAAA or BBBB , but we could do better: AAAABBBB=AAACBBB=AABBBB=AABB=AA or BB .
The foregoing indicates that the exclusion of doubles blindly is not necessarily a continuation, but nevertheless it was covered.
Instead, it seems that the most important property of the string is heterogeneity. If the line is uniform, stop, we can do nothing. Otherwise, define an operation that preserves the heterogeneity property if possible. I argue that it is always possible to identify an operation that preserves heterogeneity if the string is heterogeneous and has a length of four or more.
Proof: if a 4-substring contains two different letters, a third letter can be entered at the border between two different letters, for example, AABA goes into ACA . Since one or the other original letter must be invariable somewhere inside the string, it follows that the result is still heterogeneous.
Suppose instead that we have a 4-substring that has three different elements, such as AABC , with the outer two elements different. Then, if the middle two elements are different from each other, perform an operation on them; the result is heterogeneous because the two outer elements are still different. On the other hand, if two internal elements are the same, for example, ABBC , then they must be different from both external elements (otherwise we will only have two elements in a set of four, not three). In this case, perform the first or third operation; which leaves either the last two elements different (for example, ABBC=CBC ), or the first two different elements (for example, ABBC=ABA ), so unevenness persists.
Finally, consider the case where the first and last elements are the same. Then we have a situation like ABCA . The middle two elements both should be different from the outer elements, otherwise in this case we will have only two elements, not three. We can take the first available operation ABCA=CCA , and the heterogeneity persists again.
The end of the proof.
We have a greedy algorithm for cutting any heterogeneous string 4 or longer in length: select the first operation that preserves the heterogeneity; such an operation must exist by the argument above.
Now we came down to the case when we have a heterogeneous string of three elements. If the two are the same, we either have doublings like AAB , etc. Which, as we know, can be reduced to one element or we have two elements without a double type ABA=AC=B , which can also be reduced to one element, or we have three different elements, such as ABC . There are six permutations, all of which =1 in the group of associativity and commutativity; all of them can be reduced to two elements by any operation; however, they cannot be reduced below a homogeneous pair ( AA , BB or CC ), since 1 not allowed in the problem, so we know that the best we can do in this case.
So, if the string is uniform, we can do nothing; if the string is heterogeneous and =A in the group, it can be reduced to A in the problem by a greedy algorithm that preserves heterogeneity at every step; the same if the string =B or =C in the group; finally, if the string is heterogeneous and =1 in the group, it can be reduced using the greedy algorithm, which keeps the unevenness as long as possible to one of AA , BB or CC . This is the best we can do with the group properties of the operation.
The program that solves the problem:
Now, since we know the possible results, our program can work in O(n) time as follows: if all the letters in a given string are the same, then reduction is impossible, so just print the length of the string. If the string is heterogeneous and equal to one in the group, print number 2; otherwise print number 1.
, , : A 's, B C A , B , C . a = a mod 2 , b = b mod 2 , c = c mod 2 , AA , BB CC . A , B , C 0, ABC=1 , 2, 1 . A , B , C 0, ( A , B C ), 2 , 1.