A string S consisting of exactly n+1 X's and n O's is called semi-balanced, iff every non-empty prefix of S has more X's than O's.
For example:
XXO is semi-balanced while OXX is not.
XXOXO is semi-balanced but XOXOX is not.
This puzzle is in two parts.
a) Show that for any string S consisting of exactly n+1 X's and n O's, there is exactly one cyclic shift of $S$ which is semi-balanced.
For example if S = OXX, its cyclic shifts are OXX, XOX and XXO, the last one being semi-balanced.
b) Given S consisting of exactly n+1 X's and n O's, can you given an algorithm to determine, in O(n) time, which cyclic shift of S is semi-balanced?
[Solution]
No comments:
Post a Comment