Improving Time Bound of this Algorithm past $O(n^2)$
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.