Author: | Anton Trygub |
Suppose that we will form subsequences "AB", subsequences "AC", subsequences "BC", and let cnt_A, cnt_B, cnt_C be the numbers of times "A", "B", "C" appear in , correspondingly. Then cnt_A = X+Y, cnt_B = X+Z, cnt_C = Y+Z, so we get X = \frac{cnt_A+cnt_B-cnt_C}{2}, Y = \frac{cnt_A-cnt_B+cnt_C}{2}, Z = \frac{-cnt_A+cnt_B+cnt_C}{2}. If these values are negative/aren't integers, there is clearly no way to split the string in the desired way.
Otherwise, we found our X, Y, Z. Look at the occurences of "B": it's going to appear times in "AB", as the second letter, and times in "BC", as the first letter. Clearly, it's optimal to use first occurrences of "B" in subsequences "BC", and last in subsequences "AB". Also, we want to take as "right" "A"s as possible in "AB" and as "left" "C" as possible in "BC", as we will have to form subsequences "AC" after.
So, for each of the first occurrences of "B", we will match it with the first yet unused occurrence of "C" to the right of it, if there exists any, and for each of the last occurrences of "B", we will match it with the last yet unused occurrence of "A" to the left of it, if there exists any. As for remaining characters, we just have to check if the given string of "A"s and "C" can be split into subsequences "AC". If for some the -th occurrence of "A" goes after the -th occurrence of "C", there is no solution, otherwise match -th occurrence of "A" with the -th occurrence of "C" for each .