  Dynamic time warping distance (DTW) is a widely used distance measure between
time series $x, y \in \Sigma^n$. It was shown by Abboud, Backurs, and Williams
that in the \emph{binary case}, where $|\Sigma| = 2$, DTW can be computed in
time $O(n^{1.87})$. We improve this running time $O(n)$.
  Moreover, if $x$ and $y$ are run-length encoded, then there is an algorithm
running in time $\tilde{O}(k + \ell)$, where $k$ and $\ell$ are the number of
runs in $x$ and $y$, respectively. This improves on the previous best bound of
$O(k\ell)$ due to Dupont and Marteau.
