It can be proved that ALL “AB”s can be used in the optimal solution. (1) If the final string starts with 'A', we can put all unused “AB”s at the very beginning. (2) If the final string starts with 'B' (meaning) it starts with “BB”, we can put all unused “AB”s after the 2nd 'B'.

Using “AB” doesn’t increase the number of “AA”s or “BB”s we can use. If we put an “AB” after “BB”, then we still need to append “AA” as before, so it doesn’t change the state.

We only need to consider strings “AA” and “BB”; we can either use the pattern “AABBAABB…” or the pattern “BBAABBAA…”, depending on which one of x and y is larger.