  We give an $\tilde O(n^2)$ time algorithm for computing the exact Dynamic
Time Warping distance between two strings whose run-length encoding is of size
at most $n$. This matches (up to log factors) the known (conditional) lower
bound, and should be compared with the previous fastest $O(n^3)$ time exact
algorithm and the $\tilde O(n^2)$ time approximation algorithm.
