Improving Time Bound of this Algorithm past $O(n^2)$

Question

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 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.

Answer 1

Here is a hint. Suppose the sequence contains $n-1$ Xs and $n+1$ Ys, so that you need to change some Y to X. You can compute for each position $k \in [1,\ldots,2n]$ the number of Xs minus the number of Ys; let's call that a "report". Changing a Y to an X affects the report in a certain, easy to describe, way. On the other hand, whether a sequence is good corresponds to a very simple property of the report.

Putting everything together, you should get an $O(n)$ algorithm.