Order-Preserving Squares in Strings

Paweł Gawrychowski, Samah Ghazawi, Gad M. Landau

An order-preserving square in a string is a fragment of the form $uv$ where $u\ne v$ and $u$ is order-isomorphic to $v$. We show that a string $w$ of length $n$ over an alphabet o…