In this paper about Levine's hat puzzle there is a better strategy with a winning probability of $0.7$.
Let $a_i$ be the coin toss outcomes that are told to $A$, and $b_i$ the ones that are given to $B$. This is a bit easier than having the tosses interleaved as a single sequence.
The strategy is as follows:
Now let's calculate the probability of winning.