I recently came across the following interesting problem - one is given a sequence of X
s and Y
s such as XXYXYXYYXYXXXYX
, and consider a sequence to be good if, as you start at the left and move right, the number of X
s is greater than or equal to the number of Y
s 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 X
to Y
or a single Y
to 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
to Y
or Y
to X
) given the condition at the end that the number of X
and Y
must be equal.