4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ More appropriate for cs.stackexchange. $\endgroup$ Nov 18, 2012 at 19:44

1 Answer 1

7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.