$b$ unmarked ones, and the string $t$ contains $c$ unmarked zeros and $d$ unmarked ones.

By Claim \[claim:mark to infl\], the only coordinates that may contribute to ${{\sf distance}}({\psi}^{-1}(z),{\psi}^{-1}(z+e_i))$ are the unmarked coordinates in $s$ and $t$, and so $${{\sf distance}}({\psi}^{-1}(z),{\psi}^{-1}(z+e_i))
    =
    {{\sf distance}}({\psi}^{-1}(0^a 1^b \circ 0 \circ 0^c 1^d \circ z_{n+1}),{\psi}^{-1}(0^a 1^b \circ 1 \circ 0^c 1^d \circ z_{n+1})).$$ Therefore, it is enough to upper bound the right hand side by $5$. We first note that $a+c+1 \le b+d$. To see this recall that $|z| > n/2$ and $0^a 1^b \circ 0 \circ 0^c 1^d$ was obtain from $x = z_1\ldots z_n$ (that is, $z$ without its last bit $z_{n+1}$) by deleting the same number of zeros and ones.

\[claim:case analysis2\] For every $a,b,c,d \in {{\mathbb N}}$ such that $a+c+1 \leq b+d$, and for every $z_{n+1} \in \{0,1\}$ it holds that $${{\sf distance}}({\psi}^{-1}(0^a 1^b \circ 0 \circ 0^c 1^d \circ z_{n+1}),
    {\psi}^{-1}(0^a 1^b \circ 1 \circ 0^c 1^d \circ z_{n+1})) \leq 5.$$

Therefore, by Claim \[claim:case analysis2\] we have ${{\sf maxStretch}}({\psi}^{-1}) \leq 5$. This completes the proof of Theorem \[thm:main\].

Proof of Missing Claims {#sec:missing claims}
-----------------------

We now return to the proofs of Claim \[claim:case analysis1\] and Claim 