Problem: Let $\leftarrow$ denote the left arrow key on a standard keyboard. If
one opens a text editor and types the keys
``ab$\leftarrow$ cd $\leftarrow \leftarrow$ e $\leftarrow \leftarrow$ f'',
the result is ``faecdb''.
We say that a string $B$ is \emph{reachable} from a string $A$ if
it is possible to insert some amount of $\leftarrow$'s in $A$,
such that typing the resulting characters produces $B$.
So, our example shows that ``faecdb'' is reachable from ``abcdef''.

Prove that for any two strings $A$ and $B$,
$A$ is reachable from $B$ if and only if $B$ is reachable from $A$.

Solution: Obviously $A$ and $B$ should have the
same multiset of characters, and we focus only on that situation.

\begin{claim*}
  If $A = 123 \dots n$
  and $B = \sigma(1) \sigma(2) \dots \sigma(n)$
  is a permutation of $A$,
  then $B$ is reachable if and only if
  it is \textbf{213-avoiding},
  i.e.\ there are no indices $i < j < k$
  such that $\sigma(j) < \sigma(i) < \sigma(k)$.
\end{claim*}
\begin{proof}
  This is clearly necessary.
  To see its sufficient, one can just type $B$ inductively:
  after typing $k$, the only way to get stuck is if
  $k+1$ is to the right of $k$ and there is some character in the way;
  this gives a 213 pattern.
\end{proof}

\begin{claim*}
  A permutation $\sigma$ on $\{1, \dots, n\}$
  is 213-avoiding if and only if the inverse $\sigma\inv$ is.
\end{claim*}
\begin{proof}
  Suppose $i < j < k$ and $\sigma(j) < \sigma(i) < \sigma(k)$.
  Let $i' = \sigma(j)$, $j' = \sigma(i)$, $k' = \sigma(k)$;
  then $i' < j' < k'$ and $\sigma\inv(j') < \sigma\inv(i') < \sigma\inv(k')$.
\end{proof}

This essentially finishes the problem.
Suppose $B$ is reachable from $A$.
By using the typing pattern,
we get some permutation $\sigma \colon \{1, \dots, n\}$
such that the $i$th character of $A$
is the $\sigma(i)$th character of $B$,
and which is 213-avoiding by the claim.
(The permutation is unique if $A$ has all distinct characters,
but there could be multiple if $A$ has repeated ones.)
Then $\sigma\inv$ is 213-avoiding too
and gives us a way to change $B$ into $A$.