MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Improving Time Bound of this Algorithm past O(n^2) [closed]

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.

-
 This is a pleasant problem, but it is not research-level. Please see the FAQ. Accordingly, I have voted to close. Here is a suggestion to help you towards a linear-time solution (assuming constant time arithmetic!): Build an array A, the same length as the given word, where the entry A[i] contains the number of X's in the prefix of length i, minus the number of Y's. – Sam Nead Nov 18 at 16:58 If anything works, then either changing the first $Y$ to an $X$ or the last $X$ to a $Y$ works. So you just need to check those two. – Will Sawin Nov 18 at 19:52