I recently came across the following interesting problem - one is given a sequence of
Ys such as
XXYXYXYYXYXXXYX, and consider a sequence to be good if, as you start at the left and move right, the number of
Xs is greater than or equal to the number of
Ys at any point except at the very end, at which the two quantities must be equal.
One must determine the number of points at which changing either a single
Y or a single
X in a given sequence will yield a good sequence.
I initially considered traveling through the sequence linearly and checking if toggling the letter at that point would yield a good sequence, however that approach is on the order of $O(n\cdot n)=O(n^2)$ in the worst case where n is the length of the sequence. However, I was wondering if there was some faster method to do it.
EDIT: I made the observation that for any sequence, if the number of possible changes is greater than 0, than only one type of change will work (either changing an
X) given the condition at the end that the number of
Y must be equal.