I recently came across the following interesting problem - one is given a sequence of Xs and 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 X to Y or a single Y to X in a given sequence will yield a good sequence.
I initially considered travelling 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*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.
