Solution to finding the semi-balanced string, algorithm puzzle

This is a solution to finding the semi-balanced string algorithm puzzle.

A brief description:

Given a string S consisting of exactly (n+1) X's and n O's, show that there is exactly one cyclic shift of S which is semi-balanced, and give an O(n) time algorithm to find it.

A string is semi-balanced iff every non-empty prefix contains more X's than O's.

This property can actually be used to show that Catalan numbers are $\dfrac{\binom{2n}{n}}{n+1}$.

Solution

---

It will be a constructive proof, giving the algorithm with the proof.

Given string S consisting of X's and O's, replace X with a $1$ and O with a $-1$.

For a prefix of length $i$, take the sum $S_i$ of the $1$'s and $-1$'s that form that prefix (basically compute #X's - #O's).

For a semi-balanced string, we must have that $S_i \gt 0$ for all $i, 1 \le i \le 2n+1$.

Note that $S_{2n+1} = 1$ for any string S consisting of $n+1$ X's and $n$ O's.

Now suppose a cyclic shift left by $k$ of S gave a semi-balanced string.

Then we must have that (look at the prefix of the shift from $k+1$ to $j$)

$S_j - S_k \gt 0 \quad \forall j, k \lt j \le 2n+1$

and (look at the prefix from $k+1$ to $2n+1$ and then $1$ to $j$).

$ S_{2n+1} - S_k + S_j \gt 0 \quad \forall j, 1 \le j \le k$

i.e

$S_j \gt S_k \quad \forall j \gt k$

and (note that $S_{2n+1} = 1$)

$S_j + 1 \gt S_k \quad \forall j \le k$

Thus if $ m = \min \{S_1, S_2, \dots, S_{2n+1}\}$ then there is a unique $k$: the largest $k$ such that $S_k = m$.

This easily gives an $O(n)$ time algorithm too.